Pagini recente » Cod sursa (job #958698) | Cod sursa (job #2230883) | Cod sursa (job #3171144) | Cod sursa (job #2891231) | Cod sursa (job #1280862)
#include<string>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
string s,t;
int N,M,pi[2001000],q;
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) {
rez.push_back(i-N);
q = pi[N];
}
}
int k = rez.size();
k = min(1000,k);
printf("%d\n",k);
for(int i=0;i<k;++i) {
printf("%d ",rez[i]);
}
return 0;
}