Cod sursa(job #715301)

Utilizator algotrollNume Fals algotroll Data 16 martie 2012 23:35:09
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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;
    //
    int nSubsir = sSir-sCuv+1; static unsigned int subsir_h[_SIZEM];
    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
    vector<int> v;
    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)) v.push_back(i);
        }

    //write
    printf("%d\n", v.size());
    for (int i=0; i<v.size() && i<1000 ;i++)
        printf("%d ", v.at(i));
    return 0;
}