Pagini recente » Cod sursa (job #1283725) | Cod sursa (job #2255109) | Cod sursa (job #1662150) | Cod sursa (job #2111307) | Cod sursa (job #2849732)
#include <fstream>
///#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int SIZE = 2e6+10;
ifstream in ("strmatch.in");
ofstream cout ("strmatch.out");
char s[SIZE], sf[SIZE];
int sn, sfn;
int pre[SIZE], pos[SIZE];
int cnt;
void prep()
{
int j=0;
for(int i=2; i<=sfn; i++) {
while(j && sf[i]!=sf[j+1]) j=pre[j];
if(sf[i]==sf[j+1]) {
pre[i]=++j;
}
}
///for(int i=1; i<=sfn; i++) cout<<pre[i]<<' ';
///cout<<'\n';
}
void kmp()
{
int j=0;
for(int i=1; i<=sn; i++) {
while(j && s[i]!=sf[j+1]) j=pre[j];
if(s[i]==sf[j+1]) {
++j;
if(j==sfn) {
++cnt;
if(cnt<=1000) pos[cnt]=i-sfn;
}
}
}
}
int main()
{
in>>(sf+1)>>(s+1);
sn = strlen(s+1);
sfn = strlen(sf+1);
prep();
kmp();
cout<<cnt<<'\n';
for(int i=1; i<=min(1000, cnt); i++)
cout<<pos[i]<<' ';
return 0;
}