Pagini recente » Cod sursa (job #83158) | Cod sursa (job #415150) | Cod sursa (job #2435210) | Cod sursa (job #2459890) | Cod sursa (job #2277161)
#include <bits/stdc++.h>
using namespace std;
char p[2000010], s[2000010];
int v[2000010];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", p, s);
int n = strlen(s);
int m = strlen(p);
int q = -1;
for(int i = 1; i < m; i++)
{
while(q != -1 && p[q + 1] != p[i])
q = v[q];
if(p[q + 1] == p[i])
q++;
v[i] = q;
}
int rez[1005], lr = 0;
q = -1;
for(int i = 0; i < n; i++)
{
while(q != -1 && p[q + 1] != s[i])
q = v[q];
if(p[q + 1] == s[i])
q++;
if(q == m - 1)
{
if(lr < 1000)
rez[lr] = i - m + 1;
lr++;
}
}
printf("%d\n", lr);
for(int i = 0; i < min(1000, lr); i++)
printf("%d ", rez[i]);
return 0;
}