Cod sursa(job #1799281)

Utilizator nick12nicolae mihalache nick12 Data 6 noiembrie 2016 00:10:26
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

#define DD 2000001
vector <int> ar;
void searcsh (string pat,string txt,int q)
{
    int len1 = pat.size();
    int len2 = txt.size();
    int i,j;
    int p = 0,t{0},h{1};
    for (int i = 0;i<len1-1;i++)
    h = (h*DD)%q;

    for (i = 0;i<len1;i++)
    {
        p = (DD*p + pat[i])%q;
        t = (DD*t + txt[i])%q;
    }

    for (i = 0;i<=len2 - len1;i++)
    {
        if (p == t)
        {
            for (j=0;j<len1;j++)
                if (txt[i+j] != pat[j])
                break;
            if (j == len1)
                ar.push_back(i);
        }
        if (i<len1-len2)
        {
            t = (DD*(t-txt[i]*h)) + txt[i+len2]%q;
            if (t<0)
            t+=q;
        }
    }

}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    string a,b;
    getline(cin,a);
    getline(cin,b);
    searcsh(a,b,2000000);
    printf("%d\n",ar.size());
    for (int i=0;i<ar.size();i++)
        printf("%d ",ar[i]);
    return 0;
}