Pagini recente » Cod sursa (job #1542836) | Cod sursa (job #2432283) | Cod sursa (job #268504) | Cod sursa (job #1384148) | Cod sursa (job #2062487)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 2000000 + 5;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
char T[N_MAX], P[N_MAX], key[N_MAX];
vector<int> ans;
void build_key(){
int k = 0, m = strlen(P+1); key[0] = 0;
for(int i = 2; i<=m; ++i){
while(P[i] != P[k+1] and k > 0)
k = key[k];
if(P[i] == P[k+1])
k ++;
key[i] = k;
}
}
void kmp(){
build_key();
int n = strlen(T+1), m = strlen(P+1), k = 0;
for(int i = 1; i<=n; ++i){
while(T[i] != P[k+1] and k > 0)
k = key[k];
if(T[i] == P[k+1])
++k;
if(k == m){
ans.push_back(i-m);
k = key[k];
}
}
}
int main()
{
fin >> (P+1);
fin >> (T+1);
kmp();
fout << ans.size() << "\n";
for(int i = 0; i < min(1000, (int)ans.size()); ++i)
fout << ans[i] << " ";
return 0;
}