Cod sursa(job #1511012)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 25 octombrie 2015 21:50:14
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<cstdio>
#include<cstring>
#define base 101
#define mod1 100007
#define mod2 100021
using namespace std;
char a[2000010],b[2000010],sol[2000010];
int m,n;
int verif(int p){
    int i;
    for(i=0;i<m;i++)
        if(a[i]!=b[i+p])
            return 0;
    return 1;
}
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int hash1_a=0,hash2_a=0,hash1=0,hash2=0,last1=1,last2=1,match=0,i;
    scanf("%s%s",&a,&b);
    m=strlen(a);
    n=strlen(b);
    if(m>n){
        printf("0");
        return 0;
    }
    for(i=1;i<=m-1;i++){
        last1=(last1*base)%mod1;
        last2=(last2*base)%mod2;
    }
    for(i=0;i<m;i++){
        hash1_a=(hash1_a*base+a[i])%mod1;
        hash2_a=(hash2_a*base+a[i])%mod2;
        hash1=(hash1*base+b[i])%mod1;
        hash2=(hash2*base+b[i])%mod2;
    }
    if(hash1==hash1_a&&hash2==hash2_a)
        if(verif(0)==1){
            match++;
            sol[0]=1;
        }
    for(i=m;i<n;i++){
        hash1=(((hash1-(b[i-m]*last1)%mod1+mod1)%mod1)*base+b[i])%mod1;
        hash2=(((hash2-(b[i-m]*last2)%mod2+mod2)%mod2)*base+b[i])%mod2;
        if(hash1==hash1_a&&hash2==hash2_a)
            if(verif(i-m+1)==1){
                match++;
                sol[i-m+1]=1;
            }
    }
    printf("%d\n",match);
    match=0;
    for(i=0;i<n&&match<1000;i++)
        if(sol[i]==1){
            printf("%d ",i);
            match++;
        }
    return 0;
}