Pagini recente » Cod sursa (job #1961888) | Cod sursa (job #2094967) | Cod sursa (job #1221377) | Cod sursa (job #1159112) | Cod sursa (job #1533134)
#include<stdio.h>
#include<string.h>
#define d 256
char txt[2000001],pat[2000001],sol[2000001];
int nr;
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0;
int t = 0;
int h = 1;
for (i = 0; i < M-1; i++)
h = (1LL*h*d)%q;
for (i = 0; i < M; i++)
{
p = (1LL*d*p + pat[i])%q;
t = (1LL*d*t + txt[i])%q;
}
for (i = 0; i <= N - M; i++)
{
if ( p == t )
{
/* Check for characters one by one */
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)
sol[++nr]=i;
}
if ( i < N-M )
{
t = (1LL*d*((t - 1LL*txt[i]*h)%q) + txt[i+M])%q;
if (t < 0)
t = (t + q);
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&pat,&txt);
int q = 100057;
search(pat, txt, q);
printf("%d\n",nr);
for(int i=1;i<=nr;i++) printf("%d ",sol[i]);
return 0;
}