【字符串】tire树 kmp

for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}


for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
    
    }

Oulipo - POJ 3461 - Virtual Judge (vjudge.net.cn)

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;

int ans=0;
int n,m;
char s[1000001];
char p[10001];
int ne[10001];

void kmp(){


for(int i=2,j=0;i<=n;i++){
    while(j&&p[i]!=p[j+1])j=ne[j];

    if(p[i]==p[j+1])j++;

    ne[i]=j;
}

for(int i=1,j=0;i<=m;i++){
while(j&&s[i]!=p[j+1])j=ne[j];

    if(s[i]==p[j+1])j++;

    if(j==n){ans++;
            j=ne[j];}
}

}
int main(){

int t;cin>>t;

while(t--){
        ans=0;

scanf("%s%s",p+1,s+1);
//cin>>p+1>>s+1;
n=m=0;
for(n=1;p[n];n++);
n--;
for(m=1;s[m];m++);
m--;
        //cout<<n<<" "<<m<<" ";
kmp();
cout<<ans<<endl;
}

}

Seek the Name, Seek the Fame - POJ 2752 - Virtual Judge (vjudge.net.cn)

过不了

之后还得看字符串哈希

P6018 [Ynoi2010] Fusion tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P6623 [省选联考 2020 A 卷] 树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)