Pagini recente » Cod sursa (job #1959495) | Cod sursa (job #1414416) | Cod sursa (job #1216132) | Monitorul de evaluare | Cod sursa (job #2723376)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2e6+5;
int phi[2 * NMAX];
vector<int>sol;
void kmp(string &s)
{
phi[0] = -1;
for(int i = 1 ; i < s.size() ; i++)
{
int k = i-1;
while(phi[k] != -1 && s[phi[k]+1] != s[i])
k = phi[k];
if(phi[k] == -1)
phi[i] = -1;
else
phi[i] = phi[k] + 1;
}
}
string a, b;
string s;
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
getline(fin, a);
getline(fin, b);
s = a + "$" + b;
kmp(s);
int na = a.size();
int nb = b.size();
for (int i = na + 1; i < s.size(); i++)
{
if (phi[i] == na - 1)
sol.push_back(i-2*na);
}
fout << sol.size() << '\n';
int m = min(1000, (int)sol.size());
for (int i = 0; i < m; i++)
fout << sol[i] << ' ';
fout << '\n';
return 0;
}