微网站与普通网站的区别,网站建设销售员,淄博网站建设小程序,在线自助设计平台KMP之所以线性,因为匹配的时候i是不往回走的 我们只用调整j的位置 假设在s中找t 用二元组(i,j)表示s串的[i-j1,i] 与t串的[1,j]匹配 假设s[i1]和t[j]匹配上了,就j 如果不匹配的话,我们就想办法调整j, 直到找到一个满足二元组条件的j并且t[j1]s[i] 快速调整j就是利用nxt数组的过…KMP之所以线性,因为匹配的时候i是不往回走的 我们只用调整j的位置 假设在s中找t 用二元组(i,j)表示s串的[i-j1,i] 与t串的[1,j]匹配 假设s[i1]和t[j]匹配上了,就j 如果不匹配的话,我们就想办法调整j, 直到找到一个满足二元组条件的j并且t[j1]s[i] 快速调整j就是利用nxt数组的过程, 处理nxt的方法类似与两个串之间的匹配 1 #includecstdio2 #includealgorithm3 #includecstring4 #define N 10000105 using namespace std;6 char s[N],t[N];7 int T,nxt[N],n,m,ans;8 int main()9 {
10 scanf(%d,T);
11 getchar();
12 while (T--)
13 {
14 ans0;
15 memset(nxt,0,sizeof(nxt));
16 scanf(%s%s,s1,t1);
17 nstrlen(s1),mstrlen(t1);
18 for (int i2,j0;in;i)
19 {
20 while (j0 s[j1]!s[i]) jnxt[j];
21 if (s[j1]s[i]) j;
22 nxt[i]j;
23 }
24 for (int i1,j0;im;i)
25 {
26 while (j0 s[j1]!t[i]) jnxt[j];
27 if (s[j1]t[i]) j;
28 if (jn) ans,jnxt[j];
29 }
30 printf(%d\n,ans);
31 }
32 return 0;
33 } 转载于:https://www.cnblogs.com/mrsheep/p/7856161.html
