Pagini recente » Cod sursa (job #1149904) | Cod sursa (job #2708358) | Cod sursa (job #964301) | Cod sursa (job #465212) | Cod sursa (job #1008752)
#include <cstdio>
#include <cstring>
using namespace std;
const int Nmax = 2000005;
const int M1 = 100007;
const int M2 = 100021;
const int base = 73;
char a[ Nmax ] , b[ Nmax ] , match [ Nmax ];
int hashA1,hashA2,hash1,hash2,p1=1,p2=1,nr;
int lena,lenb,gata;
void solve()
{
lena=strlen(a),lenb=strlen(b);
for(int i = 0; i < lena ; ++i){
hashA1 = (hashA1*base + a[i])%M1,
hashA2 = (hashA2*base + a[i])%M2;
if(i)
p1 = (p1 * base) % M1,// aici imi retin de cate
p2 = (p2 * base) % M2;//ori am inmultit primul element
}
if( lena > lenb ){
printf("0\n");
gata = 1;
return;
}
for(int i = 0 ;i < lena; ++i)
hash1 = ( hash1*base + b[i]) % M1,
hash2 = ( hash2*base + b[i]) % M2;
if ( hashA1==hash1 && hashA2==hash2 )
match [ 0 ] = 1, ++nr;
for(int i = lena ; i < lenb ; ++i)
{
// scot din hashuri pe b[ i - lena]
hash1 = (hash1 - (b[i-lena]*p1)%M1 + M1);
hash2 = (hash2 - (b[i-lena]*p2)%M2 + M2);
// bag in hashuri pe b[i]
hash1 = (hash1*base + b[i])%M1;
hash2 = (hash2*base + b[i])%M2;
// daca corespund hashurile avem solutie
if(hashA1==hash1 && hashA2==hash2)
match[i-lena+1] = 1,++nr;
}
}
void afish()
{
if(gata) return;
int prints = 0;
printf("%d\n",nr);
for(int i = 0; i<lenb && prints<1000; ++i )
if(match[i])
printf("%d ",i);++prints;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&a,&b);
solve();
afish();
return 0;
}