Pagini recente » Cod sursa (job #262011) | Cod sursa (job #2779448) | Cod sursa (job #2922077) | Cod sursa (job #1137902) | Cod sursa (job #795045)
Cod sursa(job #795045)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
#define MOD1 100007
#define MOD2 100021
#define P 73
#define LMAX 1005
char A[NMAX],B[NMAX];
int sol[LMAX],r;
int n,m,pi[NMAX];
int hash1,hash2,hash11,hash22,P1,P2;
inline int check(char x)
{
return (x>='0' && x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z') ;
}
void read()
{
fgets(A+1,NMAX,stdin);
fgets(B+1,NMAX,stdin);
while (check(A[n+1])) n++;
while (check(B[m+1])) m++;
}
void precompute()
{
int i;
for (i=1; i<=n; i++)
{
hash1 = ( hash1 * P + A[i] ) % MOD1;
hash2 = ( hash2 * P + A[i] ) % MOD2;
}
P1=P2=1;
for (i=1; i<n; i++)
P1 = ( P1 * P ) % MOD1, P2 = ( P2 * P ) % MOD2;
}
inline int min(int x,int y)
{
return x<y ? x : y;
}
void solve()
{
int i,val;
for (i=1; i<=n; i++)
{
hash11 = ( hash11 * P + B[i] ) % MOD1;
hash22 = ( hash22 * P + B[i] ) % MOD2;
}
if (hash1==hash11 && hash2==hash22)
sol[++r]=1;
for (i=n+1; i<=m; i++)
{
hash11 = hash11 - (P1 * B[i-n]) % MOD1 ;
if (hash11<0) hash11 += MOD1;
hash11 = ( hash11 * P + B[i] ) % MOD1;
hash22 = hash22 - (P2 * B[i-n]) % MOD2 ;
if (hash22<0) hash22 += MOD2;
hash22 = ( hash22 * P + B[i] ) % MOD2;
if (hash1==hash11 && hash2==hash22)
{
r++;
if (r<=1000)
sol[r]=i-n+1;
}
}
printf("%d\n",r);
for ( i=1, val= min ( 1000, r) ; i <= val; i++)
printf("%d ",sol[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
precompute();
solve();
return 0;
}