Cod sursa(job #715371)

Utilizator algotrollNume Fals algotroll Data 17 martie 2012 07:56:50
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<cstring>
#include<vector>

const int _SIZEM = 2000010;
const int _BASE = 1<<31;

using namespace std;
int main()
{
    //read
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    static char sir[_SIZEM], cuv[_SIZEM];
    gets(cuv); gets(sir);
    int sSir = strlen(sir), sCuv = strlen(cuv);

    //hashes
    int cuv_h=0;
    for (int i=0; i<sCuv; i++)
        cuv_h = (cuv_h + cuv[i]) % _BASE;

    static unsigned int subsir_h[_SIZEM];
    int nSubsir = sSir-sCuv+1;

    subsir_h[0]= 0;
    for (int i=0; i<sCuv; i++)
        subsir_h[0] = (subsir_h[0] + sir[i]) % _BASE;
    for (int i=1; i<=nSubsir; i++)
        subsir_h[i] = (subsir_h[i-1] - sir[i-1] + sir[i+sCuv-1]) % _BASE;

    //comparison
    int nFinds=0; vector<int> vFinds; vFinds.reserve(1000);
    for (int i=0; i<=nSubsir; i++)
        if (subsir_h[i]==cuv_h)
        {
            int j;
            for (j=0; sir[i+j]!=0 && cuv[j]!=0 && sir[i+j]==cuv[j] ;j++);
            if (j==strlen(cuv))
            {
                nFinds++;
                if (nFinds<=1000) vFinds.push_back(i);
            }
        }

    //write
    printf("%d\n", nFinds);
    for (int i=0; i<vFinds.size() ;i++)
        printf("%d ", vFinds[i]);
    return 0;
}