Pagini recente » Cod sursa (job #1839469) | Cod sursa (job #609429) | Cod sursa (job #1980075) | Cod sursa (job #2286351) | Cod sursa (job #1090566)
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005
#define P1 100007
#define P2 1000013
//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 subKey1,subKey2;
int subLen;
int powConst1=1,powConst2=1;
int key1,key2;
queue<int> output;
int Hash(char st[], int pa, int pb, int k, int &powConst)
{
int r=0;
int pow=1;
for(int i=pb-1;i>=pa;--i)
{
char x=st[i];
r=(r+x*pow)%k;
powConst=pow;
pow=(pow*128)%k;
}
return r;
}
int main()
{
scanf("%s\n%s",substr,str);
subLen=strlen(substr);
int strLen=strlen(str);
if(subLen>strLen) printf("0");
else {
subKey1=Hash(substr,0,subLen,P1,powConst1);
key1=Hash(str,0,subLen,P1,powConst1);
subKey2=Hash(substr,0,subLen,P2,powConst2);
key2=Hash(str,0,subLen,P2,powConst2);
int n=0;
for(int i=0;i<strLen-subLen+1;i++)
{
if(key1==subKey1&&key2==subKey2) {
n+=1;
if(n<=1000)
output.push(i);
}
key1=((key1-(str[i]*powConst1)%P1+P1)*128+str[i+subLen])%P1;
key2=((key2-(str[i]*powConst2)%P2+P2)*128+str[i+subLen])%P2;
}
printf("%d\n",n);
while(!output.empty())
{
printf("%d ",output.front());
output.pop();
}
}
return 0;
}