Pagini recente » Cod sursa (job #1620502) | Cod sursa (job #2491380) | Cod sursa (job #2646129) | Cod sursa (job #212034) | Cod sursa (job #2561947)
#include <bits/stdc++.h>
#define Dim 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int dp[Dim],dpp[Dim],N,M,K,ans,S[1001];
char A[Dim],B[Dim];
int main()
{
f>>A>>B;
N=strlen(A); M=strlen(B);
for(int i=N-1;i>=0;i--) A[i+1]=A[i];
for(int i=M-1;i>=1;i--) B[i+1]=B[i];
dp[1]=0;
for(int i=2;i<=N;i++)
{
K=dp[i-1];
while( K > 0 && A[i] != A[ K + 1 ] ) K=dp[K];
if( A[i] == A[ K + 1 ] ) dp[i]=K+1;
}
dpp[0]=0;
for(int i=1;i<=M;i++)
{
K=dpp[i-1];
while( K > 0 && B[i] != A[ K + 1 ] ) K=dp[K];
if( B[i] == A[ K + 1 ] ) dpp[i]=K+1;
if( dpp[i] == N )
{
ans++;
if(ans<=100) S[ans]=i-N;
}
}
g<<ans<<'\n';
for(int i=1;i<=ans;i++) g<<S[i]<<' ';
return 0;
}