字符串-白红宇

字符串

阅读量：5126 次

发布时间：2019-06-13

本文共 2378 字，大约阅读时间需要 7 分钟。

KMP

#include 
    
     #include 
     
      #define R registerconst int MAXN=1000007;int l,l1;char s[MAXN],s1[MAXN];int fail[MAXN];inline void get_next(){    int p=0;    for(R int i=2;i<=l;++i)    {        while(p>0&&s[i]!=s[p+1]) p=fail[p];        if(s[i]==s[p+1]) p++;        fail[i]=p;    }}inline void kmp(){    int p=0;    for(R int i=1;i<=l1;++i)    {        while(p>0&&s[p+1]!=s1[i]) p=fail[p];        if(s[p+1]==s1[i]) p++;        if(p==l)        {            printf("%d\n",i-l+1);            p=fail[p];        }    }}int main(){    scanf("%s%s",s1+1,s+1);    l=strlen(s+1);    l1=strlen(s1+1);    get_next();    kmp();    for(int i=1;i<=l;++i)        printf("%d ",fail[i]);    return 0;}

字典树，trie树

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n;struct node {    int next[27];    bool w;} a[300000];int tot;bool flag[300000];void build(char *b) {    int p=0,len=strlen(b);    for(int i=0; i

马拉车

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=11000007;char s[maxn],S[maxn];int p[maxn<<1];int main(){    scanf("%s",s);    S[0]='@';S[1]='#';    int l=1,i=-1;    while(s[++i]!='\0')        S[++l]=s[i],S[++l]='#';    int mx=0,id=0,ans=0;    for(int i=1;i<=l;++i)    {        if(mx>i) p[i]=min(p[id*2-i],mx-i);//id*2-i即i-k        else p[i]=1;        while(S[i+p[i]]==S[i-p[i]]) p[i]++;        if(mx

AC自动机

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=2000100;struct Tree{ int fail,end; int vis[27]; }e[N]; int cnt,n;char s[N];inline int read() { int n=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0') {n=n*10+ch-'0';ch=getchar();} return n*f;}inline void insert(char *s) { int n=strlen(s); int now=0; for(int i=0;i

q; for(int i=0;i<26;++i) if(e[0].vis[i]) q.push(e[0].vis[i]),e[e[0].vis[i]].fail=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<26;++i) if(e[u].vis[i]) { e[e[u].vis[i]].fail=e[e[u].fail].vis[i]; q.push(e[u].vis[i]); } else e[u].vis[i]=e[e[u].fail].vis[i]; }}inline void query(char *s) { int l=strlen(s); int now=0,ans=0; for(int i=0;i

>s,insert(s); build(); cin>>s; query(s); return 0; }

转载于:https://www.cnblogs.com/dsrdsr/p/9916638.html

你可能感兴趣的文章