1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int next[10010], sum;
char ch[10010], s[1000010];
void get_next(char *p) {
    int i, j;
    i = 0;
    j = -1;
    next[0] = -1;
    while (i < strlen(p)) {
        if (j==-1 || p[i]==p[j]) {
            i++;
            j++;
            if (p[i] != p[j]) next[i] = j;
            else next[i] = next[j];
        }
        else j = next[j];
    }
}
void index_kmp(char *p, char *x) {
    int i = -1;
    int j = -1;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX