Pagini recente » Cod sursa (job #841924) | Cod sursa (job #845262) | Cod sursa (job #330985) | Cod sursa (job #1164275) | Cod sursa (job #2444842)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
int presuf[2000005], lpat, ltxt;
vector<int> ans;
void calcPS(string pat){
int st = 0, dr = 1;
while(dr < lpat){
if(pat[st] == pat[dr]){
presuf[dr] = st + 1;
st++;
dr++;
}
else{
if(st > 0) st = presuf[st - 1];
else dr++;
}
}
}
void KMP(string pat, string txt){
calcPS(pat);
int i = 0, j = 0;
while(j < ltxt){
if(pat[i] == txt[j]){
i++;
j++;
}
if(i == lpat){
ans.push_back(j - i);
i = presuf[i - 1];
}
else if(j < ltxt && pat[i] != txt[j]){
if(i > 0) i = presuf[i - 1];
else j++;
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string word, phrase;
fin >> word >> phrase;
lpat = int(word.size());
ltxt = int(phrase.size());
calcPS(word);
KMP(word, phrase);
fout << ans.size() << "\n";
for(int i = 0; i < min(1000, int(ans.size())); ++i)
fout << ans[i] << " ";
return 0;
}