Pagini recente » Cod sursa (job #21229) | Cod sursa (job #65231) | Cod sursa (job #3250158) | Cod sursa (job #2793466) | Cod sursa (job #499736)
Cod sursa(job #499736)
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void calc_prefix(string a, vector<int> &prefix) {
int i, pos = 0;
prefix[1] = 0;
for (i = 2; i < a.size(); ++i)
{
while (pos && a[pos+1] != a[i])
pos = prefix[pos];
if (a[pos+1] == a[i])
++pos;
prefix[i] = pos;
}
}
void find_matches(string a, string b, vector <int> prefix, vector<int>& matches) {
int pos = 0;
for (int i = 1; i < b.size(); ++i)
{
while (pos && a[pos+1] != b[i])
pos = prefix[pos];
if (a[pos+1] == b[i])
++pos;
if (pos == a.size() - 1)
{
pos = prefix[a.size() - 1];
matches.push_back(i - a.size() + 1);
}
}
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
fin >> a;
fin >> b;
a = '3' + a;
b = '3' + b;
if (a.size() > b.size()) {
fout << 0 << endl;
}
vector<int> prefix(a.size() + 1);
calc_prefix(a, prefix);
vector<int> matches;
find_matches(a, b, prefix, matches);
fout << matches.size() << endl;
for (int i = 0; i < matches.size(); i++) {
if (i < 1000)
fout << matches[i] << " ";
}
fout << endl;
fout.close();
return 0;
}