Cod sursa(job #3257357)

Utilizator TomaVVrinceanu Toma TomaV Data 17 noiembrie 2024 14:11:57
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000000],B[2000000];
int fv[90],n,m,i,d,nr_apar,sol[2000000],sol_ind;
int valid(int a,int b)
{
    for(int i2=0;i2<m;i2++)
        if(A[a+i2]!=B[b+i2])
        return 0;
    sol_ind++;
    sol[sol_ind]=b;
    return 1;
}
int main()
{
    cin>>A>>B;
    n=strlen(B);
    m=strlen(A);
    for(i=0;i<n;i++)
    {
        if(B[i]<='9' && B[i]>='0')
            fv[B[i]-'0']=1;
        if(B[i]>='A' && B[i]<='Z')
            fv[B[i]-'A'+10]=1;
        if(B[i]>='a' && B[i]<='z')
            fv[B[i]-'a'+36]=1;
    }
    for(int j=0;j<62;j++)
        if(fv[j])
        d++;
    int dput=1;///d^m-1
    for(int z=1;z<m;z++)
        dput*=d;
    ///calculare pattern A
    int pa=0;
    for(i=0;i<m;i++)
    {
        int putere=1;
        if(A[i]>='0' && A[i]<='9')
        {
            for(int j2=1;j2<=i;j2++)
                putere*=d;
            pa=pa+(A[i]-'0')*putere;

        }
        if(A[i]>='A' && A[i]<='Z')
        {
            for(int j2=1;j2<=i;j2++)
                putere*=d;
            pa=pa+(A[i]-'A')*putere;
        }
        if(A[i]>='a' && A[i]<='z')
        {
            for(int j2=1;j2<=i;j2++)
                putere*=d;
            pa=pa+(A[i]-'a')*putere;
        }
    }
    ///calculam primul pattern de la B
    int pb=0;
    for(i=0;i<m;i++)
    {
        int putere=1;
        if(B[i]>='0' && B[i]<='9')
        {
            for(int j2=1;j2<=i;j2++)
                putere*=d;
            pb=pb+(B[i]-'0')*putere;
        }
        if(B[i]>='A' && B[i]<='Z')
        {
            for(int j2=1;j2<=i;j2++)
                putere*=d;
            pb=pb+(B[i]-'A')*putere;
        }
        if(B[i]>='a' && B[i]<='z')
        {
            for(int j2=1;j2<=i;j2++)
                putere*=d;
            pb=pb+(B[i]-'a')*putere;
        }
    }
    if(pa==pb)
        if(valid(0,0))
        nr_apar++;
    ///rolling pattern
    for(i=1;i<=n-m;i++)
    {
        int x,y;///T[K] si T[k+m]
        if(B[i-1]>='0' && B[i-1]<='9')
        x=B[i-1]-'0';
        if(B[i-1]>='A' && B[i-1]<='Z')
        x=B[i-1]-'A';
        if(B[i-1]>='a' && B[i-1]<='z')
        x=B[i-1]-'a';

        if(B[i-1+m]>='0' && B[i-1+m]<='9')
        y=B[i-1+m]-'0';
        if(B[i-1+m]>='A' && B[i-1+m]<='Z')
        y=B[i-1+m]-'A';
        if(B[i-1+m]>='a' && B[i-1+m]<='z')
        y=B[i-1+m]-'a';

        pb=(pb-x)/d+y*dput;
        if(pa==pb)
            if(valid(0,i))
            nr_apar++;
    }
    cout<<nr_apar<<endl;
    for(i=1;i<=sol_ind;i++)
        cout<<sol[i]<<' ';
    return 0;
}