[COCI 2011/2012 #4] KRIPTOGRAM：KMP 处理子串匹配问题的经典题。
对于类似子串匹配的问题，适用 KMP 需要满足如下条件：
- 若 \(S = T\)，则对于 \(S,T\) 任意两个长度相等的前缀，都必须是相等的。
- 子串相等必须满足传递性。即若 \(A = B, B =C\)，则也一定有 \(A=C\)。
例如带通配符的子串匹配无法使用 KMP，是因为不具有传递性。
具体怎么证明我不知道，但是这个是杜老师说的，所以肯定是对的！！1
于是可以考虑对于此题如何判断两个字符是否相等，可以发现用每个位置的相同前驱的位置来判断就行了，具体而言：
- 若 \(a,b\) 的相同前驱都在待匹配的串内，则必须满足前驱的位置相等。
- 若 \(a\) 的相同前驱不在串内，则 \(b\) 的相同前驱必须不存在。
其中 \(a\) 表示待匹配的串，\(b\) 表示模式串。
跑 KMP 即可，用哈希表处理前驱即可做到时间复杂度 \(O(n)\)。
另一种做法是哈希，判断方式也是根据每个位置的相同前驱的位置来设计哈希函数，大致一样此处不再赘述。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N = 2000005;
int idx = 0, a[N], b[N], n, m, pre[N], x[N], y[N], ne[N];
map<string, int> ys;
string s;
bool equa(int *a, int i, int *b, int j)
{return ((i - a[i] == j - b[j]) || (b[j] == 0 && a[i] <= max(0, i - j - 1)));
}
void KMP()
{for(int i = 2, j = 0; i <= m; i++){while(j && !equa(y, i, y, j + 1)) j = ne[j];if(equa(y, i, y, j + 1)) j++;ne[i] = j;}for(int i = 2, j = 0; i <= n; i++){while(j && !equa(x, i, y, j + 1)) j = ne[j];if(equa(x, i, y, j + 1)) j++;if(j == m){cout << i - m + 1;return;}}
}
int main()
{//freopen("sample.in","r",stdin);//freopen("sample.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while(cin >> s){if(s == "$") break;if(ys[s] == 0) ys[s] = ++idx;a[++n] = ys[s];}while(cin >> s){if(s == "$") break;if(ys[s] == 0) ys[s] = ++idx;b[++m] = ys[s];} for(int i = 1; i <= n; i++){x[i] = pre[a[i]];pre[a[i]] = i;}memset(pre, 0, sizeof(pre));for(int i = 1; i <= m; i++){y[i] = pre[b[i]];pre[b[i]] = i;}KMP();return 0;
}