Pagini recente » Cod sursa (job #2685176) | Cod sursa (job #1927142) | Cod sursa (job #583146) | Cod sursa (job #2731237) | Cod sursa (job #1621535)
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
#define ll long long unsigned
#define pb push_back
#define mp make_pair
char A[2000005];
char B[2000005];
int pref[2000005];
vector <int> v;
void prep(){
int i;
int l = strlen(A+1);
int q = 0;
for(i = 2;i <= l;i++){
while(q && A[q+1] != A[i]){
q = pref[q];
}
if(A[q+1] == A[i]){
q++;
}
pref[i] = q;
}
}
int kmp(){
int i;
int ans = 0;
int l = strlen(B+1);
int lm = strlen(A+1);
int q = 0;
for(i = 2;i <= l;i++){
while(q && A[q+1] != B[i]){
q = pref[q];
}
if(A[q+1] == B[i]){
q++;
}
if(q == lm){
ans++;
if(ans <= 1000){
v.pb(i-lm);
}
}
}
return ans;
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s",A+1);
scanf("%s",B+1);
prep();
printf("%d\n",kmp());
for(auto it : v){
printf("%d ",it);
}
return 0;
}