Pagini recente » Cod sursa (job #2658028) | Cod sursa (job #917910) | Cod sursa (job #2382905) | Cod sursa (job #2611910) | Cod sursa (job #1198160)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define prim 666013
#define mod1 666013
#define int64 long long
char A[2000005],B[2000005]; int64 l1,l2,k;
vector<int64> match;
bool check(int64 x){
int64 k=0;
for (int64 i=x-l1+1; i<=x; i++)
if (A[k++]!=B[i]) return false;
return true;
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s", &A, &B);
l1 = strlen(A);
l2 = strlen(B);
k=0;
int64 primp=1,i=0;
if (l1>l2) {printf("0"); return 0; }
int64 j =0; int64 hashB=0;
while (j<l1){
hashB=(hashB*prim + B[j]) % mod1;
j++;
}
int64 hashA=0;
for (i=0; i<l1; i++){
hashA=(hashA*prim + A[i]) % mod1;
if (i!=0){primp=(primp*prim) % mod1;}
}
if (hashA==hashB) if (check(l1-1)) {k++; match.push_back(0);}
for (i=l1; i<l2; i++){
hashB=((hashB-((B[i-l1]*primp)% mod1 ) + mod1) * prim +B[i]) % mod1;
if (hashA==hashB) if (check(i)) {k++; match.push_back(i-l1+1);}
}
printf("%d\n",k);
if (k>1000) k=1000;
for (i=0; i<k; i++)
printf("%d ",match[i]);
return 0;
}