Pagini recente » Cod sursa (job #1991027) | Cod sursa (job #1459110) | Cod sursa (job #2986123) | Cod sursa (job #1792363) | Cod sursa (job #2180174)
#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], total;
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())
{
if(total < 1000)
{
res.push_back(i - j + 1);
}
total ++;
}
}
}
int main()
{
f >> cuv >> sir;
make_prefix();
make_kmp();
o << total << '\n';
for(auto i: res)
o << i << ' ';
return 0;
}