Pagini recente » Cod sursa (job #1626002) | Cod sursa (job #1596002) | Cod sursa (job #1570960) | Cod sursa (job #1056351) | Cod sursa (job #709925)
Cod sursa(job #709925)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
string str, pat;
vector<int> matchPos, kmpNext;
void init()
{
kmpNext.resize(str.size());
int i = 0, j = -1;
kmpNext[0] = -1;
while (i < str.size()) {
while (j > -1 && str[i] != str[j]) j = kmpNext[j];
++i, ++j;
if (str[i] == str[j]) kmpNext[i] = kmpNext[j];
else kmpNext[i] = j;
}
}
void solve()
{
int i = 0, j = 0;
while (j < pat.size()) {
while (i > -1 && str[i] != pat[j]) i = kmpNext[i];
++i, ++j;
if (i >= str.size()) {
matchPos.push_back(j - i);
i = kmpNext[i];
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> str >> pat;
init();
solve();
fout << matchPos.size() << '\n';
for (int i = 0; i < matchPos.size(); ++i) fout << matchPos[i] << " ";
fout << endl;
fin.close();
fout.close();
}