Pagini recente » Cod sursa (job #1123000) | Cod sursa (job #1724229) | Cod sursa (job #1183612) | Cod sursa (job #2844730) | Cod sursa (job #2088040)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000005;
char pattern[NMAX], text[NMAX];
int phi[NMAX]; /// phi[i] = cel mai lung sufix din pattern care se termina in i si e si prefix pattern
int phi1[NMAX]; /// phi1[i] = cel mai lung sufix din text care se termina in i si e prefix in pattern
vector<int>ans;
void Init()
{
int lena = strlen(pattern + 1), lenb = strlen(text + 1);
for (int i = 2; i <= lena; i++)
{
int last = phi[i - 1];
while (last > 0 && pattern[i] != pattern[last + 1]) last = phi[last];
if (pattern[i] == pattern[last + 1]) phi[i] = last + 1;
else phi[i] = last;
}
for (int i = 1; i <= lenb; i++)
{
int last = phi1[i - 1];
while (last > 0 && text[i] != pattern[last + 1]) last = phi[last];
if (text[i] == pattern[last + 1]) phi1[i] = last + 1;
else phi1[i] = last;
if (phi1[i] == lena)
ans.push_back(i - lena);
}
}
int main()
{
fin >> (pattern + 1) >> (text + 1);
Init();
fout << ans.size() << "\n";
for (int i = 0; i < 1000 && i < ans.size(); i++)
fout << ans[i] << " ";
return 0;
}