Pagini recente » Cod sursa (job #325880) | Cod sursa (job #454893) | Cod sursa (job #1506331) | Cod sursa (job #1582883) | Cod sursa (job #1915517)
#include <bits/stdc++.h>
using namespace std;
char s[2000005],t[2000005];
int n,m,i,j,b[1000005],nr;
queue<int> q;
void prep()
{
i = 0; j=-1; b[0] = -1;
while (i < n)
{
while (j>=0 && s[j] != s[i]) j = b[j];
i++; j++;
b[i] = j;
}
}
void caut()
{
i = 0; j = 0;
while (i <m)
{
while (j>=0 && t[i] != s[j]) j = b[j];
j++; i++;
if (j == n)
{
nr++;
q.push(i-j);
j = b[j];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&s); n = strlen(s);
scanf("%s",&t); m = strlen(t);
nr = 0;
prep();
caut();
printf("%d\n",nr);
while (!q.empty())
{
printf("%d ",q.front()); q.pop();
}
}