Pagini recente » Cod sursa (job #1365374) | Cod sursa (job #3262118) | Cod sursa (job #893185) | Cod sursa (job #3138363) | Cod sursa (job #983727)
Cod sursa(job #983727)
#include<cstdio>
#include<cstring>
//#define mod1 100007
//101
//#define mod2 100021
//109
using namespace std;
int i, v1, v2, val1, val2, p1, p2, pt1, pt2, n, n2, nr, a[2000001];
char s[2000001], s2[2000001];
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout); nr=0;
gets(s); n=strlen(s); p1=1; p2=1; v1=0; v2=0;
for (i=n-1;i>=0;i--) {
v1=(v1+(int)s[i]*p1)%100007;
v2=(v2+(int)s[i]*p2)%100021;
if (i>0) {p1=(p1*101)%100007; p2=(p2*109)%100021;}
}
gets(s2); n2=strlen(s2); pt1=1; pt2=1; val1=0; val2=0;
if (n2<n) {printf("0\n"); return 0;}
for (i=n-1;i>=0;i--) {
val1=(val1+(int)s2[i]*pt1)%100007;
val2=(val2+(int)s2[i]*pt2)%100021;
if (i>0) {pt1=(pt1*101)%100007; pt2=(pt2*109)%100021;}
}
if ((v1==val1)&&(v2==val2)) {nr++; a[++a[0]]=0;}
for (i=n;i<n2;i++) {
val1=val1-((int)s2[i-n]*p1)%100007+100007; val1=(val1*101+s2[i])%100007;
val2=val2-((int)s2[i-n]*p2)%100021+100021; val2=(val2*109+s2[i])%100021;
if ((v1==val1)&&(v2==val2)) {nr++; a[++a[0]]=i-n+1;}
}
printf("%d\n", nr);
for (i=1;i<=a[0];i++) printf("%d ", a[i]);
printf("\n"); return 0;
}