Pagini recente » Cod sursa (job #1445147) | Cod sursa (job #252273) | Cod sursa (job #458392) | Cod sursa (job #539824) | Cod sursa (job #1414057)
#include <cstdio>
#include <cstring>
#include <queue>
#define LIM 1000
#define LMAX 2000005
using namespace std;
int nr_sol,phi[LMAX];
char S1[LMAX],S2[LMAX];
queue <int>sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",S1,S2);
int k=0;
int l1=strlen(S1)-1;
int l2=strlen(S2)-1;
for (int i=2;i<=l1;i++)
{
while (k && S1[k+1]!=S1[i])k=phi[k];
if (S1[k+1]==S1[i])k++;
phi[i]=k;
}
k=0;
for (int i=1;i<=l2;i++)
{
while (k && S1[k+1]!=S2[i])k=phi[k];
if (S1[k+1]==S2[i])k++;
if (k==l1)nr_sol++;
if (k==l1 && sol.size()<LIM)sol.push(i-l1);
}
printf("%d\n",nr_sol);
for (;!sol.empty();sol.pop())
printf("%d ",sol.front());
fclose(stdin);
fclose(stdout);
}