Pagini recente » Cod sursa (job #3256202) | Cod sursa (job #2535375) | Cod sursa (job #3242653) | Cod sursa (job #3143806) | Cod sursa (job #2375481)
#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];
void build_key(){
int m = strlen((P+1));
int k = 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;
}
}
int ans;
vector<int> vecans;
void kmp(){
int n = strlen(T+1), m = strlen(P+1);
int 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++;
if(ans <= 1000)
vecans.push_back(i-m);
k = key[k];
}
}
}
int main()
{
fin >> (P+1);
fin >> (T+1);
build_key();
kmp();
fout << ans << "\n";
for(auto v :vecans)
fout << v << " ";
fin.close();
fout.close();
return 0;
}