Pagini recente » Cod sursa (job #1631922) | Cod sursa (job #2930423) | Clasamentul arhivei de probleme | Cod sursa (job #541987) | Cod sursa (job #1588344)
#include <fstream>
#include <iostream>
using namespace std;
string text, pattern;
int prefix[2000002];
int sol[1002];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> pattern;
in >> text;
for (int i = 1; i <= pattern.size(); i++)
if (pattern[i] == pattern[prefix[i-1]])
prefix[i] = prefix[i-1] + 1;
else
prefix[i] = (pattern[i] == pattern[0]);
int nr_sol = 0;
for (int i = 0, j = 0; i <= (int)text.size() - (int)pattern.size();)
{
for (; j < (int)pattern.size(); j++)
if (text[i+j] != pattern[j])
break;
if (j == (int)pattern.size() && nr_sol <= 1000)
{
++nr_sol;
if (nr_sol <= 1000)
sol[nr_sol] = i;
}
if (j > 0)
j--;
i += (j + 1 - prefix[j]);
j = prefix[j];
}
out << nr_sol << '\n';
for (int i = 1; i <= nr_sol && i <= 1000; i++)
out << sol[i] << ' ';
out << '\n';
return 0;
}