Cod sursa(job #2111012)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 21 ianuarie 2018 16:26:36
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 kb
/*#include<bits/stdc++.h>
#define mod 666013
using namespace std;

int N;

vector <int> T[mod];

//imi definesc functia hash ca fiind h[x]=x%mod
//valorile sinonime le plasez intr-o lista inlantuita. In vectorul T pe poz i voi retine un pointer catre inceputul listei inlantuite formate din taote valorile x pentru care h[x]=i

vector<int>::iterator caut(int x)
{
    int h=x%mod;
    vector<int>:: iterator it;
    for(it=T[h].begin();it!=T[h].end();it++)
        if(*it==x) return it;
    return T[h].end();
}

inline void add(int x)
{
    int h=x%mod;
    vector<int>::iterator it=caut(x);
    if(it==T[h].end())
        T[h].push_back(x);
}


inline void sterg(int x)
{
    int h=x%mod;
    vector<int>::iterator it=caut(x);
    if(it!=T[h].end())
        T[h].erase(it);
}


void read_solve()
{
    int op,val;
    freopen("hashuri.in","r",stdin);
    freopen("hashuri.out","w",stdout);
     for(scanf("%d",&N);N;N--)
     {
         scanf("%d %d",&op,&val);
         if(op==1)
         {
             add(val);
             continue;
         }
         if(op==2)
         {
             sterg(val);
             continue;
         }
         printf("%d\n", caut(val)!=T[val%mod].end());
     }
}

int main()
{
    read_solve();
}*/


#include<bits/stdc++.h>
#define N 2000001
using namespace std;

char T[N],P[N];
int n,m,nrv;
int st[N],vf;

unsigned long putere(int d,int m)
{
    int i;
    unsigned long p=1;
    for(i=1;i<m;i++) p*=d;
    return p;
}

bool check(char *P,char *T, int k)
{
    int i;
    for(i=0;i<m;i++)
        if(P[i]!=T[k+i]) return 0;
    return 1;
}


void rabin_karp(char *T, char *P, int d, int q,int q1)
{
    int i,k;
    unsigned long h,p=0,t0=0,t1=0,p1=0;
    n=strlen(T);
    m=strlen(P);
    h=putere(d,m)%q;
    for(i=0;i<m;i++)
    {
        p=(d*p+P[i])%q;
        t0=(d*t0+T[i])%q;

        p1=(d*p1+P[i])%q1;
        t1=(d*t1+T[i])%q1;
    }


    for(k=0;k<=n-m;k++)
    {
        if(p1==t1 && p==t0)
            if(check(P,T,k))
            {nrv++;
                    st[++vf]=k;
                  }
        t0=(t0+d*q-T[k]*h)%q;
        t0=(t0*d+T[k+m])%q;

        t1=(t1+d*q1-T[k]*h)%q1;
        t1=(t1*d+T[k+m])%q1;
    }

}



int main()
{
    int i,x=-1;
    freopen("strmatch.in","r",stdin);
    scanf("%s \n %s", P, T);
    rabin_karp(T,P,73,100007,100021);
    freopen("strmatch.out","w",stdout);
    cout<<nrv<<endl;
    for(i=1;i<=vf;++i)
        cout<<st[i]<<' ';

}