【UVA11019】Matrix Matcher

Description

Given an N × M matrix, your task is to find the number of occurences of an X × Y pattern.

Input
The first line contains a single integer t (t ≤ 15), the number of test cases.
For each case, the first line contains two integers N and M (N, M ≤ 1000). The next N lines
contain M characters each.
The next line contains two integers X and Y (X, Y ≤ 100). The next X lines contain Y characters
each.

Output

For each case, output a single integer in its own line, the number of occurrences.

Sample Input

2
1 1
x
1 1
y
3 3
abc
bcd
cde
2 2
bc
cd

Sample Output
0
2

【题意】

　　在二维文本串T中查找一个二维模板串P出现了多少次。

【分析】

　　拆分模板串P的每一行，建AC自动机。

　　拆分文本串T的每一行，在自动机中与P匹配，ct[i][j]表示以点(i,j)为左上角、与P等大的矩形有多少个对应的行与P匹配。
　　最后ct[i][j]==P的行数的i，j就是一个匹配点，ans++。
　　

　　注意：1.原本我在trie的叶子用动态数组维护了一个表示这一行是P的第几行的数组，但是超时了，后来看了LRJ的代码，改成了用一个nt[i]来表示重复的行的下一行，就A了。
　　2.注意在ct[i][j]里加的时候判断i,j是否大于0.

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxn 1010

 #define Maxl 110

 #define INF 0xfffffff

 int n,m,l,r;

 int ct[Maxn][Maxn],nt[Maxl];

 char s[Maxn][Maxn];

 char ss[Maxn];

 struct node

 {

     int fail,mark;

     int son[];

 }t[Maxn*Maxn];int tot;

 void upd(int x)

 {

     t[x].mark=;

     memset(t[x].son,,sizeof(t[x].son));

 }

 void read_trie(int tk)

 {

     scanf("%s",s[]+);

     int len=strlen(s[]+);

     for(int i=;i<=len;i++) ss[i]=s[][len-i+];

     int now=;

     for(int i=;i<=len;i++)

     {

         int ind=ss[i]-'a'+;

         if(!t[now].son[ind])

         {

             t[now].son[ind]=++tot;

             upd(tot);

         }

         now=t[now].son[ind];

         if(i==len)

         {

             if(t[now].mark) nt[tk]=t[now].mark;//我好搞笑

             t[now].mark=tk;

         }

     }

 }

 queue<int > q;

 void build_AC()

 {

     while(!q.empty()) q.pop();

     q.push();

     while(!q.empty())

     {

         int x=q.front();q.pop();

         for(int i=;i<=;i++)

         {

             if(t[x].son[i])

             {

                 t[t[x].son[i]].fail=x?t[t[x].fail].son[i]:;

                 q.push(t[x].son[i]);

             }

             else t[x].son[i]=t[t[x].fail].son[i];

         }

         if(t[t[x].fail].mark) t[x].mark=t[t[x].fail].mark;

     }

 }

 void add(int x,int y,int z)

 {

     if(x-z+>=) ct[x-z+][y]++;

     if(nt[z]!=) add(x,y,nt[z]);

 }

 void ffind()

 {

     int now;

     memset(ct,,sizeof(ct));

     for(int i=;i<=n;i++)

     {

         now=;

         for(int j=m;j>=;j--)

         {

             now=t[now].son[s[i][j]-'a'+];

             if(t[now].mark) add(i,j,t[now].mark);

         }

     }

     int ans=;

     for(int i=;i<=n;i++)

      for(int j=;j<=m;j++)

         if(ct[i][j]==l) ans++;

     printf("%d\n",ans);

 }

 void init()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%s",s[i]+);

     tot=;upd();

     scanf("%d%d",&l,&r);

     memset(nt,,sizeof(nt));

     for(int i=;i<=l;i++)

     {

         read_trie(i);

     }

     build_AC();

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         init();

         ffind();

     }

     return ;

 }

[UVA11019]

2016-07-12 15:37:53

巴特西

【UVA11019】Matrix Matcher

最新文章

热门文章