Cod sursa(job #2016152)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 28 august 2017 19:16:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

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

string P, T, S;
int Z[4000005], lengthS;

void ZAlgorithm()
{
     int left = 0;
     int right = 0;
     for(int k = 1; k < S.length(); k++) {
        if(k > right)
            {
                 left = right = k;
                 while(right < S.length() && S[right] == S[right - left])
                    right++;
                Z[k] = right - left;
                right--;
            } else {
                int k1 = k - left;
                if(Z[k1] < right - k + 1) {
                    Z[k] = Z[k1];
                } else {
                    left = k;
                    while(right < S.length() && S[right] == S[right - left])
                        right++;
                    Z[k] = right - left;
                    right--;
                }
            }
        }
}

int main()
{
    fin >> P; fin.get(); fin >> T;
    S += P; S += "$"; S += T;

    ZAlgorithm();

    int np = P.length(), answ = 0;
    for (int i = np; i < S.length(); ++i)
        if (Z[i] == np)
            answ ++;

    fout << answ << "\n";
    int cnt = 0;
    for (int i = np; i < S.length() && cnt != 1000; ++i)
        if (Z[i] == np)
            fout << i - np - 1 << " ", ++cnt;

    return 0;
}