Pagini recente » Cod sursa (job #2169739) | Cod sursa (job #2029895) | Cod sursa (job #3155883) | Cod sursa (job #160580) | Cod sursa (job #1346295)
#include <fstream>
#include <string>
#include <vector>
std::ifstream in ("strmatch.in");
std::ofstream out("strmatch.out");
std::string a, b;
std::vector<int> p, result;
unsigned i, j, last;
int main()
{
std::getline (in, a);
std::getline (in, b);
p.resize (a.length());
p[0] = 0;
last = 0;
for (i=1; i<p.size(); i++) {
while (last != 0 && a[last] != a[i]) last = p[last-1];
if (a[last] == a[i]) last++;
p[i] = last;
}
// for (i=0; i<p.size(); i++) out << p[i];
j = 0;
for (i=0; i<b.length(); i++) {
if (b[i] == a[j]) j++;
else while (j && b[i] != a[j]) j = p[j-1];
if (j == a.length()) {
result.push_back (i-a.length()+1);
j = p[j-1];
}
}
if (j == a.length()) result.push_back (i-a.length()+1);
out << result.size() << "\n";
int l = result.size(); if (l >= 1000) l = 999;
for (i=0; i<result.size(); i++) out << result[i] << " ";
}