Pagini recente » Cod sursa (job #1446677) | Cod sursa (job #1760430) | Cod sursa (job #802057) | Istoria paginii runda/brasov_12_jr/clasament | Cod sursa (job #2309976)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int DIM = 2e6 + 7;
int prefix[DIM];
vector <int> ind;
main()
{
string word;
string pattern;
in >> pattern >> word;
int n = word.size();
int m = pattern.size();
word = ' ' + word;
pattern = ' ' + pattern;
int k = 0;
for(int i = 2; i <= m; i++)
{
while(k != 0 && pattern[k + 1] != pattern[i])
k = prefix[k];
if(pattern[k + 1] == pattern[i])
k++;
prefix[i] = k;
}
k = 0;
int nr = 0;
for(int i = 1; i <= n; i++)
{
while(k != 0 && pattern[k + 1] != word[i])
k = prefix[k];
if(pattern[k + 1] == word[i])
k++;
if(k == m)
{
k = prefix[m];
nr++;
if(ind.size() < 1000)
ind.push_back(i - m);
}
}
out << nr << '\n';
for(int i : ind)
out << i << ' ';
}