Pagini recente » Cod sursa (job #1208755) | Cod sursa (job #2188731) | Cod sursa (job #185862) | Cod sursa (job #1158620) | Cod sursa (job #1209724)
#include <cstdio>
#include <cstring>
#include <vector>
#define pb push_back
const char IN[]="strmatch.in";
const char OUT[]="strmatch.out";
const int MAX = 2000014;
using namespace std;
char sir[MAX],sirsh[MAX];
int p[MAX],n,m,sol;
void prep();
void kmp();
vector <int> ans;
int main()
{
freopen( IN , "r" , stdin );
freopen( OUT , "w" , stdout );
gets(sir+1);
gets(sirsh+1);
n = strlen(sir+1);
m = strlen(sirsh+1);
prep();
kmp();
printf("%d\n",sol);
for( int i = 0 ; i < (int)ans.size() ; ++ i )
printf("%d ",ans[i]);
return 0;
}
void prep()
{
int k = 0 ;
for( int i = 2 ; i <= n ; ++ i )
{
while(k and sir[i]!=sir[k+1])
k=p[k];
if(sir[i]==sir[k+1])++k;
p[i]=k;
}
}
void kmp()
{
int q=0;
for( int i = 1 ; i <= m ; ++ i ){
while(q and sirsh[i]!=sir[q+1])
q=p[q];
if(sirsh[i]==sir[q+1])++q;
if( q==n ){
++sol;
if(sol<=1000)
ans.pb(i-n);
//else return ;
}
}
}