Pagini recente » Cod sursa (job #3280445) | Cod sursa (job #21879) | Cod sursa (job #21056) | Cod sursa (job #2969085) | Cod sursa (job #1243247)
#include <cstdio>
#define n_max_value 200005
#include <cstring>
#include <queue>
#define o_constraint 1000
#include <algorithm>
using namespace std;
char a[n_max_value],b[n_max_value];
queue <int> qu;
int t[n_max_value],no;
int n,m;
void next(){
t[1]=0;
int k=0;
for(int q=2 ;q<=m;q++){
while(k&&a[k+1]!=a[q])k=t[k];
if(a[k+1]==a[q])
k++;
t[q]=k;
}
}
void solve(){
next();
int q=0;
for(int i=1;i<=n;i++){
while(q&&a[q+1]!=b[i])
q=t[q];
if(a[q+1]==b[i])
q++;
if(q==m){
no++;
if(no<=o_constraint)
qu.push(i-m+1);
q=t[q];
}
}
}
void print(){
freopen("strmatch.out","w",stdout);
printf("%d\n",no);
while(!qu.empty()){
printf("%d ",qu.front());
qu.pop();
}
}
int main(void){
freopen("strmatch.in", "r" ,stdin);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
n=strlen(b);m=strlen(a);
solve();
print();
}