Cod sursa(job #2764651)

Utilizator Tudor_StefanaStefana Tudor Tudor_Stefana Data 21 iulie 2021 22:14:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define LMAX 2000000

using namespace std;

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

char s[2 * LMAX + 1 + 1];
int Z[2 * LMAX + 1 + 1];

int main()
{
    fin.getline(s, LMAX + 1);
    int LGA = strlen(s);
    s[ LGA ] = '$';

    fin.getline(s + LGA + 1, LMAX + 1);
    int lg = strlen(s);


    Z[0] = lg;
    int left = 0;
    int right = 0;

    for(int i = 1; i < lg; i++){
        if(i > right){
            left = i;
            right = i;

            while(right < lg && s[right] == s[right - left]){
                right++;
            }
            right--;

            Z[i] = right - left + 1;
        }

        else {
            int pI = i - left;

            if( i - 1 + Z[pI] < right ){
                Z[i] = Z[pI];
            }
            else {
                left = i;
                while(right < lg && s[right] == s[right - left]){
                    right++;
                }
                right--;

                Z[i] = right - left + 1;


            }
        }
    }

    int nrAparitii = 0;
    for(int i = LGA + 1; i < lg; i++){
        if(Z[i] == LGA){
            nrAparitii++;
        }
    }

    fout << nrAparitii << "\n";

    int afis = 0;
    for(int i = LGA + 1; i < lg; i++){
        if(Z[i] == LGA && afis < 1000){
            fout << i - (LGA + 1) << ' ';
            afis++;
        }
    }

    return 0;
}