Cod sursa(job #1982354)

Utilizator mirceagavrizimircea luca gavrizi mirceagavrizi Data 18 mai 2017 15:04:44
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 2.8 kb
int v[1001],d[1001];
#include<stdio.h>
using namespace std;
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int n1,n2,i,nr1,nr2,nr3,nr4,h,g,s,ci,j,ch,f,t;
    char c;
    scanf("%c",&c);
    n1=666013;
    n2=1000003;
    i=1;
    nr1=0;
    nr2=0;
    while(c!='\n'){
        if(c>='0'&&c<='9')
            g=c-47;
        else if(c>='A'&&c<='Z')
            g=c-54;
        else if(c>='a'&&c<='z')
            g=c-60;
        v[i]=g;
        i++;
        scanf("%c",&c);
    }
    h=i-1;
    j=0;
    for(i=h;i>=1;i--){
        if(j==0){
            nr1=nr1+v[i];
            nr2=nr2+v[i];
        }
        else{
            ci=j;
            s=1;
            while(ci!=0){
                s=s*62;
                s=s%n1;
                ci--;
            }
            nr1=(nr1+(s*v[i])%n1)%n1;
            ci=j;
            s=1;
            while(ci!=0){
                s=s*62;
                s=s%n2;
                ci--;
            }
            nr2=(nr2+(s*v[i])%n2)%n2;
        }
        j++;
    }
    scanf("%c",&c);
    j=0;
    nr3=0;
    nr4=0;
    for(i=1;i<=h;i++){
        if(c>='0'&&c<='9')
            g=c-47;
        else if(c>='A'&&c<='Z')
            g=c-54;
        else if(c>='a'&&c<='z')
            g=c-60;
        v[i]=g;
        scanf("%c",&c);
    }
    for(i=h;i>=1;i--){
        if(j==0){
            nr3=nr3+v[i];
            nr4=nr4+v[i];
        }
        else{
            ci=j;
            s=1;
            while(ci!=0){
                s=s*62;
                s=s%n1;
                ci--;
            }
            nr3=(nr3+(s*v[i])%n1)%n1;
            ci=j;
            s=1;
            while(ci!=0){
                s=s*62;
                s=s%n2;
                ci--;
            }
            nr4=(nr4+(s*v[i])%n2)%n2;
        }
        j++;
    }
    ch=h;
    h++;
    f=0;
    t=1;
    while(c!='\n'){
        if(nr1==nr3&&nr2==nr4){
            f++;
            d[f]=h-ch;
        }
        if(c>='0'&&c<='9')
            g=c-47;
        else if(c>='A'&&c<='Z')
            g=c-54;
        else if(c>='a'&&c<='z')
            g=c-60;
        v[h]=g;
        ci=ch-1;
        s=1;
        while(ci!=0){
            s=s*62;
            s=s%n1;
            ci--;
        }
        nr3=nr3+n1;
        nr3=nr3-(v[t]*s)%n1;
        nr3=(nr3*62)%n1;
        nr3=(nr3+g)%n1;
        ci=ch-1;
        s=1;
        while(ci!=0){
            s=s*62;
            s=s%n2;
            ci--;
        }
        nr4=nr4+n2;
        nr4=nr4-(v[t]*s)%n2;
        nr4=(nr4*62)%n2;
        nr4=(nr4+g)%n2;
        t++;
        h++;
        scanf("%c",&c);
    }
    printf("%d\n",f);
    for(i=1;i<=f&&i<=1000;i++)
        printf("%d ",d[i]-1);
return 0;
}