Pagini recente » Cod sursa (job #383805) | Cod sursa (job #843947) | Cod sursa (job #2984619) | Cod sursa (job #2834428) | Cod sursa (job #2238631)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
int lps[2000005], lpat, ltxt;
vector<int> ans;
void calcLPS(string pat){
int i = 1, len = 0;
while(i < lpat){
if(pat[i] == pat[len]){
len++;
lps[i++] = len;
}
else{
if(len > 0)
len = lps[len - 1];
else{
lps[i] = 0;
i++;
}
}
}
}
void KMP(string pat, string txt){
calcLPS(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 = lps[i - 1];
}
else if(j < ltxt && pat[i] != txt[j]){
if(i > 0)
i = lps[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());
KMP(word, phrase);
fout << ans.size() << "\n";
for(int i = 0; i < int(ans.size()); ++i)
fout << ans[i] << " ";
return 0;
}