Pagini recente » Cod sursa (job #246063) | Cod sursa (job #2797261) | Cod sursa (job #450186) | Cod sursa (job #1530150) | Cod sursa (job #2180165)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define MAX_SIR 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream o("strmatch.out");
int prefix[MAX_SIR];
string cuv, sir;
vector <int> res;
void make_prefix()
{
int l = cuv.size(), j = 0;
for(int i = 1; i < l; ++i)
{
while(j > 0 && cuv[i] != cuv[j])
j = prefix[j-1];
if(cuv[i] == cuv[j])
++ j;
prefix[i] = j;
}
}
void make_kmp()
{
int l = sir.size(), j = 0;
for(int i = 0; i < l; ++i)
{
while(j > 0 && cuv[j] != sir[i])
j = prefix[j-1];
if(cuv[j] == sir[i])
++ j;
if(j == cuv.size())
res.push_back(i - j + 1);
}
}
int main()
{
f >> cuv >> sir;
make_prefix();
make_kmp();
o << res.size() << '\n';
for(auto i: res)
o << i << ' ';
return 0;
}