uva 11019 Matrix Matcher

题意:给出一个n*m的字符矩阵T,你的任务是找出给定的x*y的字符矩阵P在T中出现了多少次.

思路：要想整个矩阵匹配，至少各行都得匹配。所以先把P的每行看做一个模式串构造出AC自动机，然后在T中的各行逐一匹配，找到P中每一行的所有匹配点。

只要在匹配时做一些附加操作，就可以把匹配出来的单一的行拼成矩形。用一个count[r][c]表示T中一(r,c)为右上角,与P等大的矩形中有多少个完整的行和P对应位置的行完全相同.当P的第i行出现在T的第r行,起始列编号为c时,意味着count[r-i][c]应当加1.所有匹配结束后,count[r] [c]=X的那些就是一个二维匹配点.

注意:模式串有可能相同,因此需要一个next数组来记录相同的模式串.

  1 #include<iostream>
  2 #include<string>
  3 #include<algorithm>
  4 #include<cstdlib>
  5 #include<cstdio>
  6 #include<set>
  7 #include<map>
  8 #include<vector>
  9 #include<cstring>
 10 #include<stack>
 11 #include<cmath>
 12 #include<queue>
 13 using namespace std;
 14 #define CL(x,v); memset(x,v,sizeof(x));
 15 #define INF 0x3f3f3f3f
 16 #define LL long long
 17 const int SIGMA_SIZE = 26;
 18 const int MAXNODE = 111000;
 19 const int MAXS = 150 + 10;
 20 
 21 struct ACautomata
 22 {
 23     int ch[MAXNODE][SIGMA_SIZE];
 24     int f[MAXNODE];    // fail函数
 25     int val[MAXNODE];  // 每个字符串的结尾结点都有一个非0的val
 26     int last[MAXNODE]; // 输出链表的下一个结点
 27     int next[MAXS];
 28     int sz;
 29     int count[1005][1005];
 30     void init()
 31     {
 32         sz = 1;
 33         memset(ch[0], 0, sizeof(ch[0]));
 34         memset(count,0,sizeof(count));
 35         memset(next,0,sizeof(next));
 36     }
 37 
 38     // 字符c的编号
 39     int idx(char c)
 40     {
 41         return c-'a';
 42     }
 43 
 44     // 插入字符串。v必须非0
 45     void insert(char *s, int v)
 46     {
 47         int u = 0, n = strlen(s);
 48         for(int i = 0; i < n; i++)
 49         {
 50             int c = idx(s[i]);
 51             if(!ch[u][c])
 52             {
 53                 memset(ch[sz], 0, sizeof(ch[sz]));
 54                 val[sz] = 0;
 55                 ch[u][c] = sz++;
 56             }
 57             u = ch[u][c];
 58         }
 59         if(val[u])
 60         {
 61             next[v]=val[u];
 62         }
 63         val[u] = v;
 64     }
 65 
 66     // 递归打印匹配文本串str[i]结尾的后缀,以结点j结尾的所有字符串
 67     void print(int i,int j,int x)
 68     {
 69         if(j)
 70         {
 71             if(x-val[j]+1>0)
 72                 count[x-val[j]+1][i]++;
 73             int t=val[j];
 74             while(next[t])
 75             {
 76                 t=next[t];
 77                 if(x-t+1>0)
 78                     count[x-t+1][i]++;
 79             }
 80             print(i,last[j],x);
 81         }
 82     }
 83 
 84     // 在T中找模板
 85     int find(char* T,int x)
 86     {
 87         int n = strlen(T);
 88         int j = 0; // 当前结点编号，初始为根结点
 89         for(int i = 0; i < n; i++)   // 文本串当前指针
 90         {
 91             int c = idx(T[i]);
 92             j = ch[j][c];
 93             if(val[j]) print(i,j,x);
 94             else if(last[j]) print(i,last[j],x); // 找到了！
 95         }
 96     }
 97 
 98     // 计算fail函数
 99     void getFail()
100     {
101         queue<int> q;
102         f[0] = 0;
103         // 初始化队列
104         for(int c = 0; c < SIGMA_SIZE; c++)
105         {
106             int u = ch[0][c];
107             if(u)
108             {
109                 f[u] = 0;
110                 q.push(u);
111                 last[u] = 0;
112             }
113         }
114         // 按BFS顺序计算fail
115         while(!q.empty())
116         {
117             int r = q.front();
118             q.pop();
119             for(int c = 0; c < SIGMA_SIZE; c++)
120             {
121                 int u = ch[r][c];
122                 if(!u)
123                 {
124                     ch[r][c]=ch[f[r]][c];
125                     continue;
126                 }
127                 q.push(u);
128                 int v = f[r];
129                 while(v && !ch[v][c]) v = f[v];
130                 f[u] = ch[v][c];
131                 last[u] = val[f[u]] ? f[u] : last[f[u]];
132             }
133         }
134     }
135 
136 };
137 ACautomata solver;
138 char str[1005][1005];
139 char str1[105][105];
140 int main()
141 {
142     int T;
143     scanf("%d",&T);
144     while(T--)
145     {
146         int N,M,X,Y;
147         scanf("%d%d",&N,&M);
148         for(int i=1; i<=N; i++)
149             scanf("%s",str[i]);
150         scanf("%d%d",&X,&Y);
151         for(int i=1; i<=X; i++)
152             scanf("%s",str1[i]);
153         solver.init();
154         for(int i=1; i<=X; i++)
155         {
156             solver.insert(str1[i],i);
157         }
158         solver.getFail();
159         for(int i=1; i<=N; i++)
160         {
161             solver.find(str[i],i);
162         }
163         int ans=0;
164         for(int i=1; i<=N; i++)
165             for(int j=1; j<=M; j++)
166                 if(solver.count[i][j]==X)
167                     ans++;
168         printf("%d
",ans);
169     }
170     return 0;
171 }

View Code