Pagini recente » Cod sursa (job #2224919) | Cod sursa (job #418629) | Cod sursa (job #1675545) | Cod sursa (job #1867141) | Cod sursa (job #1090552)
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005
#define P 500007
//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)
{
char x=st[i];
r=(r+x*pow)%P;
powConst=pow;
pow=(pow*128)%P;
}
return r;
}
int NextKey(int key, char A, char B)
{
return ((key-(A*powConst)%P+P)*128+B)%P;
}
int IsGood(int i)
{
for(int j=0;j<subLen/2;j+=1)
if(str[i+j]!=substr[j]||str[i+subLen-j-1]!=substr[subLen-j-1])
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;i++)
{
if(key==subKey) {
if(IsGood(i))
{
n+=1;
if(n<=1000)
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;
}