Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/ciurel_alexandru_george_325ca | Cod sursa (job #830046) | Istoria paginii utilizator/vanceavlad | Cod sursa (job #2007949)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int maxn = 2000005;
vector <int> sol;
int pi[maxn];
int main()
{
string a, b;
in >> a >> b;
//a = " " + a;
b = a + b;
b = " " + b;
int x = 0;
for(unsigned int i = 2; i < b.size(); i++)
{
while(x > 0 && b[i] != b[x + 1])
x = pi[x];
if(b[x + 1] == b[i])
{
x++;
pi[i] = x;
}
else
pi[i] = x;
}
//for(unsigned int i = 1; i < b.size(); i++)
// cerr << pi[i] << " ";
//cerr << a << " ";
for(unsigned int i = 1; i < b.size(); i++)
if(pi[i] >= (int)a.size())
sol.push_back(i - 2 * a.size());
out << sol.size() << "\n";
for(int i = 0; i <= min(999, (int)sol.size() - 1); i++)
out << sol[i] << " ";
out << "\n";
return 0;
}