Pagini recente » Cod sursa (job #2779370) | Cod sursa (job #1248911) | Istoria paginii runda/sg435346t | Cod sursa (job #96859) | Cod sursa (job #1823018)
#include<bits/stdc++.h>
#define NMax 2000005
using namespace std;
int urm[NMax], v[NMax];
char P[NMax], T[NMax];
int n, m, l, y;
void Urmatorul(char *P);
int main()
{
int i, x = -1;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", P+1);
scanf("%s", T+1);
n = strlen(T+1);
m = strlen(P+1);
Urmatorul(P);
int k = 0;
for(int i = 1; i <= n; i++)
{
while(k>0 && P[k+1] != T[i]) k = urm[k];
if(P[k+1] == T[i]) k++;
if(k == m)
v[++y] = i-m;
}
printf("%d\n", y);
for(int i=1;i<=min(y,1000);i++) printf("%d ",v[i]);
printf("\n");
return 0;
}
void Urmatorul(char *P)
{
int j = 0, x;
urm[1] = 0;
for(int x = 2; x <= m; x++)
{
while(j>0 && P[j+1] != P[x]) j = urm[j];
if(P[j+1] == P[x]) j++;
urm[x] = j;
}
}