Pagini recente » Cod sursa (job #593324) | Cod sursa (job #1730561) | Cod sursa (job #679866) | Cod sursa (job #1410170) | Cod sursa (job #1090502)
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005
#define P 10007
//CU RABIN KARP
using namespace std;
FILE* f=freopen("strmatch.in","r",stdin);
FILE* o=freopen("strmatch.out","w",stdout);
char str[NMAX],substr[NMAX];
int subKey;
int subLen;
int powConst=1;
int key;
queue<int> output;
int Hash(char st[], int pa, int pb)
{
int r=0;
int pow=1;
for(int i=pb-1;i>=pa;--i)
{
int x=st[i]-'A';
r=(r+(x*pow)%P)%P;
powConst=pow;
pow=(pow*26)%P;
}
return r;
}
int NextKey(int key, char A, char B)
{
int a=A-'A',b=B-'A';
return ((key-(a*powConst)%P+P)*26+b)%P;
}
int IsGood(int i)
{
for(int j=0;j<subLen;++j)
if(str[i+j]!=substr[j])
return 0;
return 1;
}
int main()
{
scanf("%s\n%s",substr,str);
subLen=strlen(substr);
int strLen=strlen(str);
if(subLen>strLen) printf("0");
else {
subKey=Hash(substr,0,subLen);
key=Hash(str,0,subLen);
int n=0;
for(int i=0;i<strLen-subLen+1&&n<1000;i++)
{
if(key==subKey)
if(IsGood(i))
{
n+=1;
output.push(i);
}
key=NextKey(key,str[i],str[i+subLen]);
}
printf("%d\n",n);
while(!output.empty())
{
printf("%d ",output.front());
output.pop();
}
}
return 0;
}