KMP 에 관 한 몇 가지 문제.

KMP 는 개 선 된 문자열 일치 알고리즘 입 니 다.
1. POJ 2406 은 몇 개의 길 이 를 ≤ 1000000 의 문자열 로 정 하고 각 문자열 이 최대 몇 개의 같은 하위 문자열 로 중복 연결 되 어 있 는 지 물 어 봅 니 다.예 를 들 어 ababab 는 최대 3 개의 ab 가 연결 되 어 있다.이 문 제 는 KMP 와 관 계 없 이 실제로 KMP 의 끝자리 와 길이 의 차 이 를 계산 하 는 것 이 순환 문자열 의 길이 입 니 다. 전체 길이 가 순환 문자열 의 길 이 를 정리 할 수 있 는 것 이 최종 답 입 니 다. 그렇지 않 으 면 1 을 위해 왜 냐 고 묻 지 말고 진실 한 지식 을 실천 하 세 요.

#include
#include
using namespace std;

const int maxn = 1e6 + 1000;
char s[maxn];
int prefix[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(cin >> s + 1) {
        if(s[1] == '.')
        break;
        int k = 0;
        int len = strlen(s+1);
        for(int i = 2; i <= len; i ++ ){
            while(s[i] != s[k + 1] && k) k = prefix[k];
            if(s[i] != s[k+1]) {
                prefix[i] = 0;
            }else {
                k++;
                prefix[i] = k;
            }
        }
        // for(int i = 1; i <= len; i++) {
        //     cout << i << ":" << prefix[i] << endl;
        // }
        int n = len - prefix[len];
        if(len%n == 0)
            cout << len / n <

2. POJ 2752 는 소문 자 만 포 함 된 문자열 (이 문자열 의 총 길 이 는 ≤ 400000) 을 지정 하고 모든 문자열 에서 접두사 이자 접두사 인 하위 문자열 의 길 이 를 구 합 니 다.예 를 들 어 ababcababababcabab 는 접두사 이자 접두사 인 하위 문자열: ab, abab, ababcabab, ababcababababcabab.첫 번 째 예 를 들 어 마지막 으로 prefix [18] = 9 prefix [9] = 4 prefix [4] = 2 prefix [2] = 0 이 니까 정 답 은 249 18 이 고 다른 문제 도 마찬가지 야. 왜 냐 고 묻 지 말고 실천 해.

#include
#include
using namespace std;

const int maxn = 4e5 + 50;
char s[maxn];
int prefix[maxn];

void print(int index){
    if(index){
        print(prefix[index]);
        cout << index << " "; 
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> (s + 1)) {
        int k = 0;
        int len = strlen(s + 1);
        for(int i = 2; i <= len; i++) {
            while(s[i] != s[k + 1] && k) k = prefix[k];
            if(s[i] == s[k+1]) {
                k ++;
                prefix[i] = k;
            }else 
                prefix[i] = 0;
        }
        print(len);       
        cout << endl;
    }
    return 0;
}

3. HDU 1711 은 두 개의 숫자 서열 을 제시 합 니 다. a [1], a [2], a [N], b [1], b [2], b [M] (1 < = M < = 10000, 1 < = N < = 1000000). 당신 의 임 무 는 하나의 숫자 K 만족 을 찾 는 것 입 니 다. a [K] = b [1], a [K + 1] = b [2], a [K + M - 1] = b [M].첫 번 째 줄 을 입력 하면 T 조 의 테스트 데이터 가 있 습 니 다. 각 조 의 테스트 데 이 터 는 세 줄 이 있 습 니 다. 첫 번 째 줄 은 두 개의 숫자 N and M (1 < = M < = 10000, 1 < = N < = 1000000) 입 니 다. 두 번 째 줄 은 N 개의 정수 대표 a [1], a [2], a [N] 을 포함 합 니 다. 세 번 째 줄 은 M 개의 정수 대표 b [1], b [2],... b [M] 을 포함 합 니 다. 모든 숫자의 범 위 는 [- 100000, 1000000] 사이 입 니 다.문자열 일치 에 대한 전형 적 인 질문

#include
using namespace std;

const int maxn1 = 1e6 + 1000;
const int maxn2 = 1e4 + 10;
int a[maxn1];

int b[maxn2];
int prefix[maxn2];

int main() {
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		for (int i = 1; i <= m; i++) {
			cin >> b[i];
		}
		//KMP
		int k = 0;
		for (int i = 2; i <= m; i++) {
			while (k && b[i] != b[k + 1]) k = prefix[k];
			if (b[i] != b[k + 1]) {
				prefix[i] = 0;
			}
			else {
				k++;
				prefix[i] = k;
			}
		}
		// for(int i = 1; i <= m ;i++) {
		//     cout << prefix[i] << " ";
		// }

		k = 0;
		bool flag = false;
		int j;
		for (j = 1; j <= n ; j++) {
			while (a[j] != b[k + 1] && k) k = prefix[k];
			if (a[j] != b[k + 1]) {
				k = 0;
			}
			else {
				k++;
			}
			if (k == m) {
				flag = true;
				break;
			}
		}

		cout << (flag ? j - m + 1 : -1) << endl;
	}
	//system("pause");
	return 0;
}

4. codeforce 압축 단어 라운드 \ # 578 DIV 2 E 문제
Amugae has a sentence consisting of n words. He want to compress this sentence into one word. Amugae doesn’t like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges “sample” and “please” into “samplease”.
Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.
Input The first line contains an integer n (1≤n≤105), the number of the words in Amugae’s sentence.
The second line contains n words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits (‘A’, ‘B’, …, ‘Z’, ‘a’, ‘b’, …, ‘z’, ‘0’, ‘1’, …, ‘9’). The total length of the words does not exceed 10^6
대 의 는 가능 한 한 첫 번 째 문자열 의 접 두 사 를 두 번 째 문자열 의 접두사 와 일치 시 킨 다음 에 지 워 진 새로운 문자열 을 세 번 째 문자열 과 일치 시 키 는 것 입 니 다................................................근 데 KMP 가 약간 변 형 된 KMP 인 것 같 아 요.

#include
using namespace std;

const int maxn = 1e6 + 1000;

int N = 0;
int prefix[maxn];
char s[maxn];
char S[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  
    int n;
    cin >> n;
    while(n--){
        int k = 0;
        cin >> s + 1;
        int len = strlen(s+1);
        for(int i = 2; i <= len; i++) {
            while(s[i] != s[k+1] && k) k = prefix[k];
            if(s[i] != s[k+1]) {
                prefix[i] = 0;
            }else {
                k++;
                prefix[i] = k;
            }
        }
        int j = max(1, N - len + 1);
        k = 0;
        for( ; j <= N; j++) {
            while(s[k+1] != S[j] && k) k = prefix[k];
            if(s[k+1] != S[j]) {
                k = 0;
            }else {
                k ++;
            }
        }
        for(k++; k <=len ;k ++) {
            S[++N] = s[k];
        }

    }
    for(int i = 1;i <=N;i++) cout << S[i];
    //system("pause");
}