Pagini recente » Cod sursa (job #1478445) | Cod sursa (job #1036812) | Cod sursa (job #997130) | Cod sursa (job #2242371) | Cod sursa (job #1323265)
#include<stdio.h>
#include<string.h>
using namespace std;
#define FIN "ahocorasick.in"
#define FOUT "ahocorasick.out"
#define WORDLEN 100000
#define STRINGLEN 1000000
#define ascii (int)'a'
char str[STRINGLEN];
char word[WORDLEN];
int n;
int strlength;
int compare(char word[],int index, int length)
{
for(int i=0;i<length;i++)
{
if(word[i] != str[index + i])
return 1;
}
return 0;
}
int countStr(char word[])
{
int table[26]; //bad mismatch table
int length = strlen(word);
//preprocessing
for(int i=0; i < 26; i++)
{
table[i] = length;
}
for(int i=0;i< length;i++)
table[(int)word[i] - ascii] = length - i - 1;
//comparison
int index = 0;
int counter = 0;
while(index + length <= strlength)
{
if(compare(word,index, length) == 0)
{
counter++;
index++;
}
else
{
if(table[str[index+length] - ascii] == 0)
index++;
else index += table[str[index+length] - ascii];
}
}
return counter;
}
int main()
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
gets(str);
scanf("%d ", &n);
strlength = strlen(str);
for(int i=1;i<=n;i++)
{
gets(word);
printf("%d \n",countStr(word));
}
return 0;
}