kmp
-
[백준] 4354번 문자열 제곱문제 풀이 2020. 8. 29. 15:50
4354 문자열 제곱 문제알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.a^0 = "" (빈 문자열)a^(n+1) = a*(a^n)문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오. 입력입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다. 출력각각의 테스트 케이..
-
[백준] 1786번 찾기문제 풀이 2020. 8. 28. 17:21
1786 찾기 풀이)KMP 알고리즘을 이용해서 패턴이 문자열에 일치하는 횟수와 인덱스를 출력하는 문제이다. KMP 알고리즘에 대한 설명 링크https://comyoung.tistory.com/177 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include #include #include using namespace std; #define MAX 1000003char T[MAX];char P[MAX];int F[MAX];vector match_idx; int main() {..
-
알고리즘 ch11 String match학교 수업/알고리즘 2020. 6. 16. 15:21
String- 문자의 나열- Substring : 연속되는 부분 문자열, Subsequence : 연속되지않는 부분 문자열 예시로 ACDEF와 ABKEF가 있다고 하자.substring = EF ACDEF ABKEF subsequence = AEF ACDEF ABKEF- Prefix : 문자열의 첫번째 문자부터 시작되는 부분문자열, Suffix : 문자열의 마지막문자부터 거꾸로 보는 부분문자열예시로 문자열 ALGORITHM이 있다고 하자prefix = AALALGALGO...ALGORITHMsuffix = MHMTHMITHM...ALGORITHM 본인 자기자신의 문자열을 제외하면 proper prefix, proper suffix라고 한다.예시로 설명하자면 ALGORITHM 을 제외한 것 String m..