Pagini recente » Cod sursa (job #3291) | Cod sursa (job #3360) | Cod sursa (job #14442) | Cod sursa (job #366698) | Cod sursa (job #517025)
Cod sursa(job #517025)
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> matches;
int prefix[2000001];
string a,b;
void calc_prefix(const string& a, int* prefix) {
int i, pos = 0;
prefix[1] = 0;
for (i = 2; i <= a.size(); ++i)
{
while (pos > 0 && a[pos] != a[i-1])
pos = prefix[pos];
if (a[pos] == a[i-1])
++pos;
prefix[i] = pos;
}
}
// find the first 1000 matches
void find_matches(const string& a,const string& b, int* prefix, vector<int>& matches, int* count) {
int pos = 0;
*count = 0;
for (int i = 1; i <= b.size(); ++i)
{
while (pos > 0 && a[pos] != b[i-1])
pos = prefix[pos];
if (a[pos] == b[i-1])
++pos;
if (pos == a.size())
{
(*count)++;
pos = prefix[a.size()];
if (*count <= 1000)
matches.push_back(i - a.size());
}
}
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a;
fin >> b;
if (a.size() > b.size()) {
fout << 0 << endl;
fout.close();
return 0;
}
calc_prefix(a, prefix);
matches.clear();
int count;
find_matches(a, b, prefix, matches, &count);
fout << count << endl;
for (int i = 0; i < matches.size(); i++) {
fout << matches[i] << " ";
}
fout << endl;
/*
for (int i=0; i<b.size()-a.size()+1; i++) {
bool ok = true;
for (int j=0; j<a.size(); j++)
if (a[j] != b[i+j]) ok = false;
if (ok) fout << i + 1 << " ";
}
fout << endl; */
fout.close();
return 0;
}