Pagini recente » Cod sursa (job #1586013) | Cod sursa (job #1395669) | Cod sursa (job #1093786) | Cod sursa (job #361627) | Cod sursa (job #1198155)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define prim 73
#define mod1 666013
char A[2000005],B[2000005]; int l1,l2,k;
vector<int> match;
bool check(int x){
int k=0;
for (int 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;
int primp=1,i=0;
if (l1>l2) {printf("0"); return 0; }
int j =0; int hashB=0;
while (j<l1){
hashB=(hashB*prim + B[j]) % mod1;
j++;
}
int 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 )) * prim +B[i]) % mod1;
if (hashA==hashB) if (check(i)) {k++; match.push_back(i-l1+1);}
}
printf("%d\n",k);
for (i=0; i<k; i++)
printf("%d ",match[i]);
return 0;
}