Pagini recente » Cod sursa (job #2481201) | Cod sursa (job #467733) | Cod sursa (job #300585) | Cod sursa (job #2539149) | Cod sursa (job #1495981)
#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;
}
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)
{
q.push_back(i - rad_size);
j = v[j];
}
}
g<<q.size()<<'\n';
for(int i = 0; i < q.size(); i++)
g<<q[i]<<" ";
return 0;
}