Pagini recente » Cod sursa (job #1324471) | Cod sursa (job #3169188) | Cod sursa (job #1922160) | Cod sursa (job #976111) | Cod sursa (job #2221427)
#include<fstream>
#include<cstring>
using namespace std;
string a,b;
int n,m,nrm, prefix[2000005];
bool match[2000005];
void build_prefix() {
for (int i=1; i<n; ++i) {
int k=prefix[i-1];
while (k>0 && a[i]!=a[k]) k=prefix[k-1];
if (k==0 && a[i]==a[0]) prefix[i]=1;
else if (k>0) prefix[i]=k;
}
}
int main(void) {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
getline(cin,a);
getline(cin,b);
n=a.length();
m=b.length();
build_prefix();
int idx=0;
for (int i=0; i<m; ++i) {
if (b[i]==a[idx]) ++idx;
else {
while (idx>0 && b[i]!=a[idx]) idx=prefix[idx-1];
if (b[i]==a[idx]) ++idx;
}
if (idx==n) {
++nrm;
match[i-n]=1;
idx=prefix[n-1];
}
}
cout<<nrm<<"\n";
int cnt=1000;
for (int i=0; i<m && cnt>0; ++i)
if (match[i]==1) {
cout<<i+1<<" ";
--cnt;
}
return 0;
}