Cod sursa(job #2426582)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 28 mai 2019 19:34:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#define MAX 2000001

using namespace std;

int lps[MAX], poz[MAX];

void preprocessing(string a)
{
    int i, len, m;

    len = 0;
    lps[len] = 0;

    i = 1;
    m = a.length();

    while(i < m)
    {
        if(a[i] == a[len])
        {
            len++;
            lps[i] = len;
            i++;
        }

        else
        {
            if(len != 0)
            {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int solve(string a, string b)
{
    int matches = 0;

    preprocessing(b);

    int i, j, n, m;

    i = j = 0;

    n = a.length();
    m = b.length();

    while(i < n)
    {
        if(b[j] == a[i])
        {
            j++;
            i++;
        }

        if(j == m)
        {
            poz[matches] = i - j;
            matches++;
            j = lps[m - 1];
        }

        else if(i < n && b[j] != a[i])
        {
            if(j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }

    return matches;
}

int main()
{
    string a, b;
    int matches, i;

    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    fin >> a >> b;

    matches = solve(b, a);

    fout << matches << '\n';

    for(i = 0; i < min(matches, 1000); i++)fout << poz[i] << " ";

    fin.close();
    fout.close();

    return 0;
}