首页 > 代码库 > LightOJ 题目1427 - Substring Frequency (II)(AC自己主动机)

LightOJ 题目1427 - Substring Frequency (II)(AC自己主动机)

1427 - Substring Frequency (II)
技术分享 PDF (English) Statistics Forum
Time Limit: 5 second(s) Memory Limit: 128 MB

A string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given a string T and n queries each with a string Pi, where the strings contain lower case English alphabets only. You have to find the number of times Pi occurs as a substring of T.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 500). The next line contains the string T (1 ≤ |T| ≤ 106). Each of the next n lines contains a string Pi (1 ≤ |Pi| ≤ 500).

Output

For each case, print the case number in a single line first. Then for each string Pi, report the number of times it occurs as a substring of T in a single line.

Sample Input

Output for Sample Input

2

5

ababacbabc

aba

ba

ac

a

abc

3

lightoj

oj

light

lit

Case 1:

2

3

1

4

1

Case 2:

1

1

0

Notes

1.      Dataset is huge, use faster I/O methods.

2.       If S is a string then |S| denotes the length of S.

就是问子串在母串中的出现的次数(可重叠)

ac代码

技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享技术分享

#include<stdio.h>   
#include<string.h>   
#include<queue>   
#include<iostream>   
using namespace std;  
const int  maxnode=250*1000+10000;
const int sg_size=26;  
char str[1000100],key[550];
int pos[550];
struct Trie  
{  
    int ch[maxnode][sg_size];  
    int val[maxnode];     
    int f[maxnode];   
    int num[maxnode];
    int sz;  
    void init()
	{
		sz=1;
		memset(ch,0,sizeof(ch));
		memset(val,0,sizeof(val));
		memset(f,0,sizeof(f));
		memset(num,0,sizeof(num));
	}
    int idx(char c)  
    {  
        return c-‘a‘;  
    }  
    int insert(char *s)  
    {  
        int u=0,i;  
        for(i=0;s[i];i++)  
        {  
            int c=idx(s[i]);  
            if(!ch[u][c])  
                ch[u][c]=sz++;;
            u=ch[u][c];  
        }  
        val[u]++;  
        num[u]=0;  
        return u;  
    } 
    void build_ac()  
    {  
        queue<int>q;  
        int i;  
        for(i=0;i<sg_size;i++)  
        {  
            if(ch[0][i])  
                q.push(ch[0][i]);  
        }  
        int r,c,u,v;  
        while(!q.empty())  
        {  
            r=q.front();  
            q.pop();  
            for(c=0;c<sg_size;c++)  
            {  
                u=ch[r][c];  
                if(!u)  
                    continue;  
                q.push(u);  
                v=f[r];  
                while(v&&ch[v][c]==0)  
                    v=f[v];      
                f[u]=ch[v][c];  
            }  
        }  
    }  
    void find(char *s)  
    { 
        int j=0;  
        for(int i=0;s[i];i++)  
        {  
            int c=idx(s[i]);  
            while(j&&ch[j][c]==0)  
                j=f[j];  
            j=ch[j][c];  
            int temp=j;  
            while(temp)  
            {  
                num[temp]++;  
                temp=f[temp];  
            }  
        }  
    } 
}ac;  
int main()
{
	int t,c=0;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);	
		scanf("%s",str);
		int i;
		ac.init();
		for(i=1;i<=n;i++)
		{
			scanf("%s",key);
			pos[i]=ac.insert(key);
		}  
		ac.build_ac();
		ac.find(str);
		printf("Case %d:\n",++c);
		for(i=1;i<=n;i++)
		{
			printf("%d\n",ac.num[pos[i]]);
		}
	}
}


LightOJ 题目1427 - Substring Frequency (II)(AC自己主动机)