Pagini recente » Cod sursa (job #2562231) | Cod sursa (job #2885020) | Cod sursa (job #787737) | Cod sursa (job #1473143) | Cod sursa (job #983995)
Cod sursa(job #983995)
#include<cstdio>
#include<cstring>
//#define mod1 100007
//101
//#define mod2 100021
//109
using namespace std;
int min(int a, int b){if (a<=b) return a; else return b;}
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<=min(a[0] 1000); i++) printf("%d ", a[i]);
printf("\n");
return 0;
}