Pagini recente » Cod sursa (job #2055049) | Cod sursa (job #941180) | Cod sursa (job #386593) | Cod sursa (job #1760573) | Cod sursa (job #1495983)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define mm 2000005
int v[mm];
string rad,sur;
vector<int> q;
int main()
{
f >> rad >> sur;
int rad_size = rad.size();
int sur_size = sur.size();
for(int i = rad_size; i > 0; i--) rad[i] = rad[i-1];
for(int i = sur_size; i > 0; i--) sur[i] = sur[i-1];
for(int i = 2, j = 0; i <= rad_size; i++)
{
while(j and rad[i] != rad[j+1])
j = v[j];
if (rad[i] == rad[j+1])
j++;
v[i] = j;
}
int cn = 0;
for(int i = 1, j = 0; i <= sur_size; i++)
{
while(j and sur[i] != rad[j+1])
j = v[j];
if (sur[i] == rad[j+1])
j++;
if (j == rad_size and cn < 1000)
{
q.push_back(i - rad_size);
cn = q.size();
j = v[j];
}
}
g<<q.size()<<'\n';
for(int i = 0; i < min(1000,cn); i++)
g<<q[i]<<" ";
return 0;
}