Pagini recente » Cod sursa (job #882583) | Cod sursa (job #221071) | Cod sursa (job #1392479) | Cod sursa (job #2165556) | Cod sursa (job #1280863)
#include<string>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
string s,t;
int N,M,pi[2001000],q,k;
vector<int> rez;
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin>>s>>t;
N = s.size();
M = t.size();
s.insert(0," ");
t.insert(0," ");
q = 0;
for(int i=2;i<=N;++i) {
while(q && s[q+1] != s[i]) {
q = pi[q];
}
if(s[q+1] == s[i]) {
++q;
}
pi[i] = q;
}
q = 0;
for(int i=1;i<=M;++i) {
while(q && s[q+1]!=t[i]) {
q = pi[q];
}
if(s[q+1] == t[i]) {
++q;
}
if(q==N) {
if(k<1000) {
rez.push_back(i-N);
++k;
} else {
break;
}
q = pi[N];
}
}
printf("%d\n",k);
for(int i=0;i<k;++i) {
printf("%d ",rez[i]);
}
return 0;
}