Pagini recente » Cod sursa (job #1087055) | Cod sursa (job #3145482) | Cod sursa (job #2436634) | Cod sursa (job #688781) | Cod sursa (job #3348965)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[2000009], s2[2000009];
int lps[2000009];
signed main ()
{
f.getline (s1+1, 2000001);
f.getline (s2+1, 2000001);
int x=0;
int l1=strlen(s1+1);
int l2=strlen(s2+1);
for (int i=2; i<=l1; i++)
{
x=lps[i-1];
while (x && s1[x+1]!=s1[i])
x=lps[x];
if (s1[x+1]==s1[i])
lps[i]=x+1;
}
vector <int> ans;
x=0;
for (int i=1; i<=l2; i++)
{
while (x && s1[x+1]!=s2[i])
x=lps[x];
if (s1[x+1]==s2[i])
x++;
if (x==l1)
ans.push_back(i-l1);
}
g << ans.size()<<'\n';
for (int i=0; i<min (int(ans.size()), 1000); i++)
g <<ans[i]<< ' ';
}