Cod sursa(job #1982364)

Utilizator mirceagavrizimircea luca gavrizi mirceagavrizi Data 18 mai 2017 15:22:05
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 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,ci,j,ch,f,t,s1,s2;
    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;
    ci=h-1;
    s1=1;
    while(ci!=0){
        s1=s1*62;
        s1=s1%n1;
        ci--;
    }
    ci=h-1;
    s2=1;
    while(ci!=0){
        s2=s2*62;
        s2=s2%n2;
        ci--;
    }
    j=1;
    g=1;
    for(i=h;i>=1;i--){
        nr1=(nr1+(j*v[i])%n1)%n1;
        nr2=(nr2+(g*v[i])%n2)%n2;
        j=j*62;
        j=j%n1;
        g=g*62;
        g=g%n2;
    }
    scanf("%c",&c);
    j=1;
    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);
    }
    g=1;
    for(i=h;i>=1;i--){
        nr3=(nr3+(j*v[i])%n1)%n1;
        nr4=(nr4+(g*v[i])%n2)%n2;
        j=j*62;
        j=j%n1;
        g=g*62;
        g=g%n2;
    }
    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;
        nr3=nr3+n1;
        nr3=nr3-(v[t]*s1)%n1;
        nr3=(nr3*62)%n1;
        nr3=(nr3+g)%n1;
        nr4=nr4+n2;
        nr4=nr4-(v[t]*s2)%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;
}