Pagini recente » Cod sursa (job #97626) | Cod sursa (job #3150177) | Cod sursa (job #2750872) | Clasament simularea_lui_xutzu | Cod sursa (job #2061360)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
const int N_MAX = 2000000 + 5;
int f[N_MAX];
void build_f(string pattern)
{
int m = pattern.size(), i, j;
f[0] = f[1] = 0;
for(i = 2; i <= m; i++) {
j = f[i - 1];
for( ; ; ) {
if(pattern[j] == pattern[i - 1]) {
f[i] = j + 1; break;
}
if(j == 0) {
f[i] = 0;
break;
}
j = f[j];
}
}
}
vector <int> ans;
void kmp(string text, string pattern)
{
int n = text.size(), m = pattern.size(), i, j;
build_f(pattern);
i = 0, j = 0;
for( ; ; ) {
if(j == n) break;
if(text[j] == pattern[i]) {
i++;
j++;
if(i == m)
ans.push_back(j-m);
}
else if(i > 0)
i = f[i];
else j++;
}
}
string text, pattern;
int main()
{
fin >> pattern >> text;
kmp(text, pattern);
int total_sol = min((int)ans.size(), 1000);
fout << total_sol << "\n";
for(int i = 0; i<total_sol; ++i)
fout << ans[i] << " ";
return 0;
}