Cod sursa(job #1970438)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 19 aprilie 2017 12:37:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.94 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

typedef pair<int, int> pii;

class RabinKarp
{
private:
    int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
    int base[2] = {137, 139};
    string a, b;

public:
    RabinKarp () {a = ""; b = "";}
    RabinKarp (string _a, string _b) {a = _a; b = _b;}

    vector<int> solve()
    {
        vector <int> ans;
        ans.clear();

        int N = a.size();
        int M = b.size();
        if(N > M)   return ans;

        pii hshA = {0, 0};
        pii hshB = {0, 0};
        pii pw = {1, 1};
        for(int i = 0; i < N; i++)
        {
            char c;

            c = a[i];
            hshA.first = ((1LL * hshA.first * base[0]) % mod[0] + c) % mod[0];
            hshA.second = ((1LL * hshA.second * base[1]) % mod[1] + c) % mod[1];

            c = b[i];
            hshB.first = ((1LL * hshB.first * base[0]) % mod[0] + c) % mod[0];
            hshB.second = ((1LL * hshB.second * base[1]) % mod[1] + c) % mod[1];

            pw.first = (1LL * pw.first * base[0]) % mod[0];
            pw.second = (1LL * pw.second * base[1]) % mod[1];
        }

        if(hshA == hshB)    ans.push_back(0);

        for(int i = N; i < M; i++)
        {
            char c;
            c = b[i];
            hshB.first = ((1LL * hshB.first * base[0]) % mod[0] + c) % mod[0];
            hshB.second = ((1LL * hshB.second * base[1]) % mod[1] + c) % mod[1];

            c = b[i - N];
            hshB.first = (hshB.first - (1LL * c * pw.first) % mod[0] + mod[0]) % mod[0];
            hshB.second = (hshB.second - (1LL * c * pw.second) % mod[1] + mod[1]) % mod[1];

            if(hshA == hshB)    ans.push_back(i - N + 1);
        }

        return ans;
    }
};

class KMP
{
private:
    string a, b;

public:
    KMP() {a = ""; b = "";}
    KMP(string _a, string _b) {a = _a; b = _b;}

    vector<int> solve()
    {
        vector <int> ans;
        ans.clear();

        int N = a.size();
        int M = b.size();
        if(N > M)   return ans;

        a.push_back(0);
        vector <int> phi;
        phi.resize(N + 5);
        int l = 0;
        for(int i = 1; i < N; i++)
        {
            while(l && a[l] != a[i])
                l = phi[l - 1];

            if(a[l] == a[i])    l++;
            phi[i] = l;
        }

        l = 0;
        for(int i = 0; i < M; i++)
        {
            while(l && a[l] != b[i])
                l = phi[l - 1];

            if(a[l] == b[i])    l++;
            if(l >= N)  ans.push_back(i - N + 1);
        }

        return ans;
    }
};

class ZAlgo
{
private:
    string a, b;

public:
    ZAlgo() {a = ""; b = "";}
    ZAlgo(string _a, string _b) {a = _a; b = _b;}

    vector<int> solve()
    {
        vector <int> ans;
        ans.clear();

        int N = a.size();
        int M = b.size();
        if(N > M)   return ans;

        string c = a + b;
        vector <int> z;
        c.push_back(0);
        z.resize((int)c.size() + 5);
        int lst = 0, pmax = 0;
        for(int i = 1; i < c.size(); i++)
        {
            if(pmax >= i)
                z[i] = min(z[i - lst], pmax - i + 1);

            z[i]++;
            while(c[ z[i] - 1 ] == c[ i + z[i] - 1 ])
                z[i]++;
            z[i]--;

            if(i + z[i] - 1 > pmax)
            {
                pmax = i + z[i] - 1;
                lst = i;
            }

            if(i >= N && z[i] >= N)
                ans.push_back(i - N);
        }
        return ans;
    }
};

char a[2000005], b[2000005];

int main()
{
    #ifdef FILE_IO
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    #endif

    gets(a); gets(b);

    KMP kmp( (string)a, (string)b );
    auto ans = kmp.solve();

    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size() && i < 1000; i++)
        printf("%d ", ans[i]);

    return 0;
}