Pagini recente » Cod sursa (job #592132) | Cod sursa (job #1104537) | Cod sursa (job #2404245) | Cod sursa (job #2292286) | Cod sursa (job #2444837)
#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]) dr++;
else{
while(dr < lpat && pat[st] == pat[dr]){
presuf[dr] = st + 1;
dr++;
st++;
}
st = presuf[st - 1];
}
}
}
void KMP(string pat, string txt){
calcPS(pat);
int pos = 0;
for(int i = 0; i < ltxt; ++i){
if(pat[pos] == txt[i]){
if(pos == lpat - 1){
ans.push_back(i - pos);
pos = 0;
i--;
}
else pos++;
}
else pos = presuf[pos - 1];
}
}
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;
}