Cod sursa(job #2416893)

Utilizator aurelionutAurel Popa aurelionut Data 28 aprilie 2019 15:06:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <string>
#include <fstream>
#include <vector>

using namespace std;

vector <int> sol, z(4000005);
string a, b, c;

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> a >> b;
    c = a + "$" + b;
    int left = 0, right = 0;
    for (int i = 1;i < c.length();++i)
    {
        if (i > right)
        {
            left = right = i;
            while (right < c.length() && c[right] == c[right - left])
                ++right;
            z[i] = right - left;
            --right;
        }
        else
        {
            int p = i - left;
            if (z[p] < right - i + 1)
                z[i] = z[p];
            else
            {
                left = i;
                while (right < c.length() && c[right] == c[right - left])
                    ++right;
                z[i] = right - left;
                --right;
            }
        }
    }
    int cnt = 0;
    for (int i = a.length();i < c.length();++i)
    {
        if (z[i] == a.length())
        {
            ++cnt;
            if (cnt <= 1000)
                sol.push_back(i - a.length() - 1);
        }
    }
    fout << cnt << "\n";
    for (int i = 0;i < sol.size();++i)
        fout << sol[i] << " ";
    fin.close();
    fout.close();
    return 0;
}