KMP

getNext()函数，分析T数组自身的前后缀匹配的性质，计算出T数组的回溯位置

next[i]表中记录的是字符串中的每个子串的最大相等前后缀的长度

以aabaaf为例子

第一个子串是t0=“a”，易知该子串没有前缀也没有后缀，故next[0]=0
第二个子串是t1=“aa”，该子串的前缀为"a"，后缀也为"a"，故next[1]=1
第三个子串是t2=“aab”，该子串的后缀中一定会有"b"，前缀中一定不含有"b"，则其没有相等的前后缀，故next[2]=0
第四个子串是t3=“aaba”，该子串的最大相等前后缀为"a"，长度为1，故next[3]=1
第五个子串是t4=“aabaa”，该子串的最大相等前后缀为"aa"，长度为2，故next[4]=2
第六个子串是t5=“aabaaf”，该子串的后缀中一定会有"f"，前缀中一定不含有"f"，则其没有相等的前后缀，故next[5]=0

j 0 1 2 3 4 5
T a a b a a f
next 0 1 0 1 2 0 
1
2
3
4
5
6
7
8
9
10
void getnext(char T[], int next[]) {
	int j = 0;
	next[0] = 0;
	int len = strlen(T);
	for (int i = 1; i < len; i++) {
		while (j > 0 && T[i] != T[j])j = next[j - 1];
		if (T[i] == T[j])j++;
		next[i] = j;
	}
}
1
2
3
4
5
6
7
8
for (int i = 0; i < Source.length(); i++) {
			while (j > 0 && S[i] != T[j])j = next[j - 1];
			if (S[i] == T[j])j++;
			if (j == len2) {//匹配到了一个，自己决定写些啥
				cnt++;
				j = next[j - 1];
			}
		}

有限自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define lenT length(T)
#define conNum 26
int dp[lenT][conNum];
void FSM(char T[]) {
    int len = strlen(T);
    dp[0][T[0] - 'a'] = 1;
    int x = 0;
    for (int j = 1; j < len; j++) {
        for (int c = 0; c < conNum; c++) {
            if (T[j] - 'a' == c)dp[j][c] = j + 1;
            else dp[j][c] = dp[x][c];
        }
        x = dp[x][T[j] - 'a'];
    }
}

int search(char S[],int lenT){
    int len = strlen(S);
    int j=0;
    for(int i = 0; i < len;i++){
        j = dp[j][S[i]-'a'];
        if(j==lenT)return i-j+1;
    }
}