字符串（一）

KMP

int main(){
    cin>>s1;
    cin>>s2;
    int n=strlen(s1);
    int m=strlen(s2);
    nxt[0]=0;
    int j=0;
    for(int i=1;i<m;i++){
        while(j>0&&s2[i]!=s2[j])j=nxt[j];
        if(s2[i]==s2[j]){
            j++;
        }
        nxt[i+1]=j;
    }
    j=0;
    for(int i=0;i<n;i++){
        while(j>0&&s1[i]!=s2[j])j=nxt[j];
        if(s1[i]==s2[j]){
            j++;
        }
        if(j==m){
            cout<<i-m+2<<endl;
        }
    }
    for(int i=1;i<=m;i++){
        cout<<nxt[i]<<" ";
    }
    cout<<endl;
    return 0;
}

manacher

// d[i]: 以位置 i 为中心的最长回文串的半径长度
s+='#';
for(int i=0;i<ss.size();i++){
    s+=ss[i];
    s+='#';
}
int n=s.size();
for(int i=0,l=0,r=-1;i<n;i++){
    int k=(i>r)?1:min(d[l+r-i],r-i+1);
    while(0<=i-k&&i+k<n&&s[i-k]==s[i+k])k++;
    d[i]=k--;
    if(i+k>r){
        l=i-k;
        r=i+k;
    }
    ans=max(ans,d[i]-1);
}

Trie

int ch[N][26],tot;
bool bo[N];
void insert(char *s){
    int len=strlen(s);
    int u=0;
    for(int i=0;i<len;i++){
        int c=s[i]-'a';
        if(ch[u][c]==-1){
            ch[u][c]=++tot;
        }
        u=ch[u][c];
    }
    bo[u]=true;
}
bool find(char *s){
	int len=strlen(s);
	int u=1;
	for(int i=0;i<len;i++){
		int c=s[i]-'a';
		if(ch[u][c]==-1)return false;
		u=ch[u][c];
	}
  	return true;
}
int main(){
    memset(ch,-1,sizeof(ch));
}