Cod sursa(job #1867456)

Utilizator andysoloAndrei Solo andysolo Data 4 februarie 2017 09:33:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <cstring>
#include <cmath>
#define NMAX 2000000
#define M101 666013
#define M109 10003

using namespace std;

ifstream a("strmatch.in");
ofstream b("strmatch.out");

struct key { int b101 ; int b109 ;};
struct key sir[NMAX], sub;
int k,l[NMAX];
char sir1[NMAX],sub1[NMAX];

int pww(int x,int t)
{
    int p=1;
    for(int i=1;i<=t;i++)
        p*=x;
    return p;
}

int main()
{
    a>>sub1>>sir1;
    int m=strlen(sub1);
    int n=strlen(sir1);

    for(int i=0;i<m;i++)
        {
            int x=pww(101,m-i-1);
            sub.b101 += sub1[i]*pww(101,m-i-1);
            sub.b109 += sub1[i]*pww(109,m-i-1);
        }
    sub.b101 %= M101;
    sub.b109 %= M109;

    for(int i=0;i<m;i++)
        {
            sir[m-1].b101 += sir1[i]*pww(101,m-i-1);
            sir[m-1].b109 += sir1[i]*pww(109,m-i-1);
        }
    sir[m-1].b101 %= M101;
    sir[m-1].b109 %= M109;

    long long int P101 = pww(101,m-1);
    long long int P109 = pww(109,m-1);

    for(int i=m;i<n;i++)
        {
            sir[i].b101 = ((( sir[i-1].b101 - (int)sir1[i-m]*P101)%M101 + M101 )*101 + sir1[i] )%M101;
            sir[i].b109 = ((( sir[i-1].b109 - (int)sir1[i-m]*P109)%M109 + M109 )*109 + sir1[i] )%M109;
            if(sir[i].b101==sub.b101 && sir[i].b109==sub.b109)
            {
                bool ok=true;
                for(int k=i-m+1,u=0;k<=i;k++,u++)
                    if(sir1[k]!=sub1[u])
                    ok=false;
                if(ok)
                    {
                        l[++k]=i-m+1;
                    }
            }
        }
        b<<k<<endl;
        for(int i=1;i<=k;i++)
            b<<l[i]<<" ";


            return 0;
}