Pagini recente » Cod sursa (job #2692910) | Cod sursa (job #2730790) | Cod sursa (job #3227256) | Cod sursa (job #2320253) | Cod sursa (job #3291820)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[2000009], t[2000009];
int lps[2000009];
vector <int> ans;
int main ()
{
f.getline (s+1, sizeof(s));
f.getline (t+1, sizeof(t));
int l1=strlen (s+1);
for (int i=2; i<=l1; i++)
{
if (s[i]==s[1])
{
int j=1;
while (s[i]==s[j] && i<=l1)
lps[i]=j, i++, j++;
i--;
}
}
int j=0, i=1;
int l2=strlen(t+1);
while (i<=l2)
{
while (j<l1 && s[j+1]==t[i]) i++, j++;
if (j==l1)
{
int poz=i-l1-1;
ans.push_back(poz);
j=0;
i=i-l1+1;
continue;
}
if (s[j+1]!=t[i])
{
if (j) j=lps[j];
else i++;
}
}
g << ans.size() << '\n';
for (int i=0; i<min ((int)ans.size(), 1000); i++)
g << ans[i] << ' ';
}