字符串匹配算法小结

最近刷字符串被各种虐……

以前学过kmp，当时完全没有理解，也不会运用。。于是这次重新学了一遍……

具体实现什么的就不说了。我看的这篇文章：http://blog.csdn.net/liuben/article/details/4409505

（只是不知道为什么用他的代码跑出来的next数组是错了。。。应该是我太弱了）

还有一篇zbox的文章：http://blog.chinaunix.net/uid-20338639-id-1964950.html

然后一道单串匹配的裸题：hdu1711

各种膜拜crf大神 140ms...

kmp:

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 using namespace std;
 5 #define maxn 1000010
 6 #define maxm 10010
 7 
 8 int s[maxn],p[maxm],next[maxm],t,n,m;
 9 
10 void get_next()
11 {
12     next[1]=0;
13     int j=0;
14     for (int i=2;i<=m;++i)
15     {
16         while (j&&p[i]!=p[j+1]) j=next[j];
17         if (p[i]==p[j+1]) next[i]=++j;
18     }
19 }
20 int kmp()
21 {
22     int j=0;
23     for (int i=1;i<=n;++i)
24     {
25         while (j&&s[i]!=p[j+1]) j=next[j];
26         if (s[i]==p[j+1]) ++j;
27         if (j==m) return i-m+1;
28     }
29     return -1;
30 }
31 
32 int main()
33 {
34     scanf("%d",&t);
35     while (t--)
36     {
37         memset(next,0,sizeof(next));
38         scanf("%d%d",&n,&m);
39         for (int i=1;i<=n;i++) scanf("%d",&s[i]);
40         for (int i=1;i<=m;i++) scanf("%d",&p[i]);
41         get_next();
42         printf("%d\n",kmp());
43     }
44     return 0;
45 }

zbox:

View Code

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 using namespace std;
 5 #define maxn 1010010
 6 #define min(a,b) (a)<(b)?(a):(b)
 7 int n,m,s[maxn],z[maxn];
 8 
 9 int get_zbox(int len)
10 {
11     int l,r=0;
12     for (int k=2;k<=len;k++)
13     {
14         z[k]=(k<=r)?min(z[k-l+1],r-k+1):0;
15         for (;s[z[k]+k]==s[z[k]+1];z[k]++);
16         if (z[k]+k-1>r) r=z[k]+k-1,l=k;
17         if (k>m && z[k]>=m) return k-m-1;
18     }
19     return -1;
20 }
21 
22 int main()
23 {
24     int _=0;
25     scanf("%d",&_);
26     while (_--)
27     {
28         scanf("%d%d",&n,&m);
29         for (int i=m+2;i<=m+n+1;i++) scanf("%d",&s[i]);
30         for (int i=1;i<=m;i++) scanf("%d",&s[i]);
31         s[m+1]=1000001;
32         printf("%d\n",get_zbox(m+n+1));
33     }
34 }

另外一道：poj2185

给出一个矩阵，要求用一个小矩阵将其覆盖（允许超出边界），求小矩阵的最小面积

先横着对每一行处理出next数组，找到最小循环节（=n-next[n]，理解next数组之后画一下图就知道了），找到最小公倍数。再竖着同样做一遍，乘起来就可以了。可惜跑得奇慢无比。。。

View Code

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define maxn 10010
 7 #define maxm 80
 8 
 9 char a[maxn][maxm];
10 int n,m,next[maxn];
11 
12 int get_row(int x)
13 {
14     memset(next,0,sizeof(next));
15     int j=0;
16     for (int i=2;i<=m;i++)
17     {
18         while (j&&a[x][i]!=a[x][j+1]) j=next[j];
19         if (a[x][i]==a[x][j+1]) next[i]=++j;
20     }
21     return m-next[m];
22 }
23 int get_column(int x)
24 {
25     memset(next,0,sizeof(next));
26     int j=0;
27     for (int i=2;i<=n;i++)
28     {
29         while (j&&a[i][x]!=a[j+1][x]) j=next[j];
30         if (a[i][x]==a[j+1][x]) next[i]=++j;
31     }
32     return n-next[n];
33 }
34 int gcd(int x,int y)
35 {
36     while (x%=y^=x^=y^=x);
37     return y;
38 }
39 
40 int main()
41 {
42     scanf("%d%d\n",&n,&m);
43     for (int i=1;i<=n;i++)
44     {
45         for (int j=1;j<=m;j++)
46             scanf("%c",&a[i][j]);
47         scanf("\n");
48     }
49     int A=1,B=1;
50     for (int i=1;i<=n;i++)
51     {
52         int t=get_row(i);
53         A=A*t/gcd(A,t);
54         A=A>m?m:A;
55         if (A==m) break;
56     }
57     for (int i=1;i<=m;i++)
58     {
59         int t=get_column(i);
60         B=B*t/gcd(B,t);
61         B=B>n?n:B;
62         if (B==n) break;
63     }
64     printf("%d\n",A*B);
65     return 0;
66 }

hdu4468

定义串B是由串A的若干前缀加在一起再加上串A本身构成的。现在给出串B，求串A的最小长度。

贪心+kmp。尝试去构造串A，假设我们现在由B构造出了串A的一部分，用B去匹配A。如果B读到一个串A中从未出现过的字符，就把上次构造或完全匹配之后到当前的所有字符加进构造的串A里，更新A的next数组。最后再把结尾没有匹配的字符全部加进A里。

中间有一部分没有想到……卡了很久……

View Code

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 using namespace std;
 5 #define maxn 100010
 6 
 7 int next[maxn],n,m;
 8 char s[maxn],c[maxn];
 9 
10 void init()
11 {
12     memset(next,0,sizeof(next));
13     memset(c,0,sizeof(c));
14     c[1]=s[1];
15     m=1;
16 }
17 void get_next()
18 {
19     int j=0;
20     while (j&&c[m]!=c[j+1]) j=next[j];
21     if (c[m]==c[j+1]) next[m]=++j;
22 }
23 void match()
24 {
25     int j=0,l;
26     for (int i=1;i<=n;i++)
27     {
28         while (j&&s[i]!=c[j+1]) j=next[j];
29         if (s[i]==c[j+1]) ++j;
30         if (!j)
31         {
32             for (int k=l;k<=i;k++)
33                 c[++m]=s[k],get_next();
34             l=i+1;
35         }
36         else if (j==m) l=i+1;
37     }
38     m+=(n-l+1);
39 }
40 
41 int main()
42 {
43     int Case=0;
44     while (~scanf("%s",s+1))
45     {
46         for (n=1;s[n];n++);
47         n--;
48         init();
49         match();
50         printf("Case %d: %d\n",++Case,m);
51     }
52     return 0;
53 }

以前以为ac自动机非常高端，现在觉得ac自动机比kmp好理解。还是给出一篇文章：http://blog.csdn.net/niushuai666/article/details/7002823

一道裸题 hdu2222

View Code

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 
  7 #define maxn 500010
  8 
  9 struct node
 10 {
 11     int flag;
 12     node *fail,*next[26];
 13     node ()
 14     {
 15         fail=NULL;
 16         flag=0;
 17         for (int i=0;i<26;i++)
 18             next[i]=NULL;
 19     }
 20 }*q[maxn],*root;
 21 int n,cnt,t;
 22 char a[55],c[1000010];
 23 
 24 void init()
 25 {
 26     root=new node();
 27     cnt=0;
 28 }
 29 void insert(int len)
 30 {
 31     node *p=root;
 32     for (int i=0;i<len;i++)
 33     {
 34         int t=(int)(a[i])-97;
 35         if (p->next[t]==NULL) p->next[t]=new node();
 36         p=p->next[t];
 37     }
 38     p->flag++;
 39 }
 40 void build()
 41 {
 42     int op=0,cl=0;
 43     q[++cl]=root;
 44     while (op!=cl)
 45     {
 46         node *p=q[++op];
 47         for (int i=0;i<26;i++)
 48         {
 49             if (p->next[i]!=NULL)
 50             {
 51                 if (p==root)
 52                     p->next[i]->fail=root;
 53                 else
 54                 {
 55                     node* tmp=p->fail;
 56                     while (tmp!=NULL)
 57                     {
 58                         if (tmp->next[i]!=NULL)
 59                         {
 60                             p->next[i]->fail=tmp->next[i];
 61                             break;
 62                         }
 63                         tmp=tmp->fail;
 64                     }
 65                     if (tmp==NULL)
 66                         p->next[i]->fail=root;
 67                 }
 68                 q[++cl]=p->next[i];
 69             }
 70         }
 71     }
 72 }
 73 void ac(int len)
 74 {
 75     node *p=root;
 76     for (int i=0;i<len;i++)
 77     {
 78         int t=(int)(c[i])-97;
 79         while (p->next[t]==NULL && p!=root) p=p->fail;
 80         p=p->next[t];
 81         if (p==NULL) p=root;
 82         node *tmp=p;
 83         while (tmp!=root && tmp->flag)
 84         {
 85             cnt+=tmp->flag;
 86             tmp->flag=0;
 87             tmp=tmp->fail;
 88         }
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     scanf("%d",&t);
 95     while (t--)
 96     {
 97         init();
 98         scanf("%d",&n);
 99         for (int i=1;i<=n;i++)
100         {
101             int l=0;
102             scanf("%s",a);
103             for (;a[l];l++);
104             insert(l);
105         }
106         build();
107         scanf("%s",c);
108         int l;
109         for (l=0;c[l];l++);
110         ac(l);
111         printf("%d\n",cnt);
112     }
113 }

另一道裸题 hdu3065

开始以为字符集要开到128，但是我开到128MLE了。。。后来才发现模式串只包含大写字母。。。

View Code

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 using namespace std;
  5 #define maxm 50010
  6 #define maxn 1010
  7 #define maxl 2000010
  8 
  9 struct node
 10 {
 11     int id;
 12     node *fail,*next[26];
 13     node()
 14     {
 15         id=0;
 16         fail=NULL;
 17         for (int i=0;i<26;i++)
 18             next[i]=NULL;
 19     }
 20 }*root,*q[maxm];
 21 int n,cnt[maxn];
 22 char s[maxn][55],a[maxl];
 23 
 24 void init()
 25 {
 26     memset(cnt,0,sizeof(cnt));
 27     root=new node();
 28 }
 29 void insert(char *c,int l,int id)
 30 {
 31     node *p=root;
 32     for (int i=0;i<l;i++)
 33     {
 34         int t=(int)c[i]-65;
 35         if (p->next[t]==NULL) p->next[t]=new node();
 36         p=p->next[t];
 37     }
 38     p->id=id;
 39 }
 40 void build()
 41 {
 42     int op=0,cl=0;
 43     q[++op]=root;
 44     while (op!=cl)
 45     {
 46         node *p=q[++cl];
 47         for (int i=0;i<26;i++)
 48             if (p->next[i]!=NULL)
 49             {
 50                 if (p==root)
 51                     p->next[i]->fail=root;
 52                 else
 53                 {
 54                     node *tmp=p->fail;
 55                     while (tmp!=NULL)
 56                     {
 57                         if (tmp->next[i]!=NULL)
 58                         {
 59                             p->next[i]->fail=tmp->next[i];
 60                             break;
 61                         }
 62                         tmp=tmp->fail;
 63                     }
 64                     if (tmp==NULL) p->next[i]->fail=root; 
 65                 }
 66                 q[++op]=p->next[i];
 67             }
 68     }
 69 }
 70 void ac(int l)
 71 {
 72     node *p=root;
 73     for (int i=0;i<l;i++)
 74     {
 75         int t=(int)a[i]-65;
 76         if (t<0 || t>25)
 77         {
 78             p=root;
 79             continue;
 80         }
 81         while (p->next[t]==NULL && p!=root)
 82             p=p->fail;
 83         p=p->next[t];
 84         if (p==NULL) p=root;
 85         node *tmp=p;
 86         while (tmp!=root && tmp->id)
 87         {
 88             cnt[tmp->id]++;
 89             tmp=tmp->fail;
 90         }
 91     }
 92 }
 93 
 94 int main()
 95 {
 96     while (~scanf("%d",&n))
 97     {
 98         init();
 99         for (int i=1;i<=n;++i)
100         {
101             scanf("%s",s[i]);
102             int l;
103             for (l=0;s[i][l];l++);
104             insert(s[i],l,i);
105         }
106         scanf("\n");
107         gets(a);
108         build();
109         int l;
110         for (l=0;a[l];l++);
111         ac(l);
112         for (int i=1;i<=n;i++)
113             if (cnt[i]) printf("%s: %d\n",s[i],cnt[i]);
114     }
115     return 0;
116 }

hdu2457

给出n个病毒的DNA，再给出一段DNA，求最少的修改次数使得这段DNA中不含有任何病毒的DNA

ac自动机上的dp。。。就和图上的dp差不多。详细题解看这里：http://blog.sina.com.cn/s/blog_6fbae11201011e6d.html

话说因为数组开小的问题我调了一个晚上…果然是弱爆的节奏…

View Code

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 using namespace std;
  5 #define maxn 1010
  6 #define maxm 55
  7 #define maxl 22
  8 #define min(a,b) (a)<(b)?(a):(b)
  9 #define inf 0x3f3f3f3f
 10 
 11 int n,a[maxm][maxl],cnt,s[maxn],dp[maxn][maxn<<1];
 12 char st[maxn];
 13 struct node
 14 {
 15     int flag,num;
 16     node *fail,*next[4];
 17 }*q[maxn],*root,id[maxn];
 18 void deal(char *str,int *p)
 19 {
 20     int len=1;
 21     for (;str[len];len++)
 22     {
 23         if (str[len]=='A') p[len]=0;
 24         else if (str[len]=='T') p[len]=1;
 25         else if (str[len]=='C') p[len]=2;
 26         else p[len]=3;
 27     }
 28     p[0]=--len;
 29 }
 30 struct acautomaton
 31 {
 32     node* new_node()
 33     {
 34         node *p=&id[++cnt];
 35         p->flag=0;
 36         p->num=cnt;
 37         p->fail=NULL;
 38         for (int i=0;i<4;i++) p->next[i]=NULL;
 39         return p;
 40     }
 41     void init()
 42     {
 43         cnt=0;
 44         memset(dp,0x3f,sizeof(dp));
 45         memset(id,0,sizeof(id));
 46         root=new_node();
 47     }
 48     void insert(int *str)
 49     {
 50         node *p=root;
 51         for (int i=1;i<=str[0];i++)
 52         {
 53             int t=str[i];
 54             if (p->next[t]==NULL) p->next[t]=new_node();
 55             p=p->next[t];
 56         }
 57         p->flag=1;
 58     }
 59     void build()
 60     {
 61         int op=0,cl=0;
 62         q[++op]=root;
 63         while (op!=cl)
 64         {
 65             node *p=q[++cl];
 66             for (int i=0;i<4;i++)
 67             {
 68                 if (p->next[i])
 69                 {
 70                     if (p==root)
 71                         p->next[i]->fail=root;
 72                     else
 73                     {
 74                         node *tmp=p->fail;
 75                         while (tmp)
 76                         {
 77                             if (tmp->next[i])
 78                             {
 79                                 p->next[i]->fail=tmp->next[i];
 80                                 if (tmp->next[i]->flag==1) p->next[i]->flag=1;
 81                                 break;
 82                             }
 83                             tmp=tmp->fail;
 84                         }
 85                         if (tmp==NULL) p->next[i]->fail=root;
 86                     }
 87                     q[++op]=p->next[i];
 88                 }
 89                 else
 90                 {
 91                     if (p==root) p->next[i]=root;
 92                     else p->next[i]=p->fail->next[i];
 93                 }
 94             }
 95         }
 96     }
 97     int solve(int *str)
 98     {
 99         dp[0][1]=0;
100         node *p;
101         for (int i=1;i<=str[0];i++)
102         {
103             int t=str[i];
104             for (int j=1;j<=cnt;j++)
105             {
106                 if (dp[i-1][j]<inf)
107                     for (int k=0;k<4;k++)
108                     {
109                         if (!id[j].next[k]->flag)
110                         {
111                             p=id[j].next[k];
112                             dp[i][p->num]=min(dp[i][p->num],dp[i-1][j]+(t!=k));
113                         }
114                     }
115             }
116         }
117         int ans=inf;
118         for (int i=1;i<=cnt;i++)
119             if (ans>dp[str[0]][i]) ans=dp[str[0]][i];
120         if (ans==inf) return -1;
121         return ans;
122     }
123 }ac;
124 
125 int main()
126 {
127     int _=0;
128     scanf("%d\n",&n);
129     while (n)
130     {
131         ac.init();
132         for (int i=1;i<=n;i++)
133         {
134             char c[25];
135             scanf("%s",c+1);
136             deal(c,a[i]);
137             ac.insert(a[i]);
138         }
139         scanf("%s",st+1);
140         deal(st,s);
141         ac.build();
142         printf("Case %d: %d\n",++_,ac.solve(s));
143         scanf("%d\n",&n);
144     }
145     return 0;
146 }

我是弱菜，求轻虐……

秒客网

字符串匹配算法小结

相关文章