Cod sursa(job #1815940)

Utilizator vladm98Munteanu Vlad vladm98 Data 25 noiembrie 2016 22:41:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;
char s[4000005];
long long counter, raspuns[1001];
int z[4000005];
void Z_Algorithm (int lungime, int n)
{
    z[1] = 0;
    int l, r;
    l = r = 1;
    for (int i = 2; i<=n; ++i)
    {
        if (i > r)
        {
            while (z[i] + i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
            l = i;
            r = i + z[i] - 1;
        }
        else
        {
            if (i+z[i-l+1]-1 < r)
                z[i] = z[i-l+1];
            else
            {
                z[i] = r-i;
                while (z[i] + i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
                l = i;
                r = i + z[i] - 1;
            }
        }
        if (z[i] == lungime)
        {
            ++counter;
            if (counter <= 1000)
                raspuns[counter] = i-lungime-2;
        }
    }
}
int main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    int n, i, len;
    fin >> (s+1);
    len = strlen (s+1);
    s[len+1] = '#';
    fin >> (s+len+2);
    n = strlen(s+1);
    Z_Algorithm(len, n);
    fout << counter << '\n';
    for (int i = 1; i<=counter && i <=1000; ++i)
        fout << raspuns[i] << " ";
    return 0;
}