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