Pagini recente » Cod sursa (job #3275799) | Cod sursa (job #640512) | Cod sursa (job #746878) | Cod sursa (job #2656007) | Cod sursa (job #2335194)
#include <iostream>
#include <fstream>
using namespace std;
const int Maxx=2e6+1;
const int XXX=1e3+1;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
int ans[XXX];
int pi[Maxx];
string A,B;
void prefix(){
int i,q=0;
pi[1]=0;
for (i=2;i<=n;++i){
while (q && A[q+1]!=A[i]){
q=pi[q];
}
if (A[q+1]==A[i]){
++q;
}
pi[i]=q;
}
}
int main() {
fin>>A>>B;
n=A.size();
m=B.size();
A.insert(0," ");
B.insert(0," ");
prefix();
int q=0;
int sol=0;
for (int i=1;i<=m;++i){
while (q && A[q+1]!=B[i]){
q=pi[q];
}
if (A[q+1]==B[i]){
++q;
}
if (q==n && sol<=1000) {
ans[++sol]=i-n;
}
}
fout<<sol<<"\n";
for (int i=1;i<=sol;++i){
fout<<ans[i]<<" ";
}
return 0;
}