KMP

發表於 更新於 Disqus：

這只是模板

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> kmp(string &s) {
	int n = s.size();
	vector<int> dp(n);
	for(int i = 1, j = 0; i < n; i++) {
		while(j && s[i] != s[j])
			j = dp[j - 1];
		if(s[i] == s[j])
			j++;
		dp[i] = j;
	}
	return dp;
}

字串比對

從$t$中找有幾個子字串==$s$：

1
2
3
4
5
6
7
8
9
10
vector<int> w = kmp(s);
for(int i = 0, j =0; i < t.size(); i++) {
	while(j && t[i] != s[j])
		j = w[j - 1];
	if(t[i] == s[j])
		j++;
	if(j == s.size())
		cnt++, j = w[j - 1];
}
cout << cnt << '\n';

其他應用待補

題目