Cod sursa(job #1767493)

Utilizator GoogalAbabei Daniel Googal Data 29 septembrie 2016 11:50:19
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#define nmax 3000010

using namespace std;

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

vector<int> sol;
string a, b, rez;
int z[nmax],n,j,k,i;

int main()
{
    fin>>a>>b;
    string rez = "0";
    rez+=a;rez+='#';rez+=b;
    n = rez.length() - 1;
    k=1;
    for (i = 2; i <= n; ++i)
    {
        if (k + z[k] - 1 < i)
        {
            int p = i;
            for (j=1;p<=n && rez[p]==rez[j];++p,++j);
            z[i]=p-i;
            k=i;
        }
        else
        {
            z[i] = min(z[i - k + 1], k + z[k] - 1 - (i - 1));
            for (; z[i] + i <= n && rez[z[i] + i] == rez[z[i] + 1]; ++z[i]);
            if (i + z[i] - 1 > k + z[k] - 1)
            {
                k = i;
            }
        }
    }
    for (int i = a.length() + 1; i <= n; ++i)
    {
        if (z[i] >= a.length())
        {
            sol.push_back(i - a.length() - 2);
        }
    }
    fout << sol.size() << '\n';
    for (int i = 0; i < min(1000,int (sol.size())); ++i)
    {
        fout << sol[i] << ' ';
    }
    return 0;
}