Cod sursa(job #3204794)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 17 februarie 2024 14:28:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.67 kb
//Algoritmul lui Z -  Complexitate O(n)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
string pattern,text;
long long sol;
int Z[4000003];
vector <int> V;
void construct_Z(string S,int Z[]);

// prints all occurrences of pattern in text using Z algo
void solve(string text, string pattern)
{
    // Create concatenated string "P$T"
    string concatenat='0'+pattern+text;
    int l=concatenat.length()-1;

    // Construct Z array
    construct_Z(concatenat,Z);

    // now looping through Z array for matching condition
    for(int i=pattern.size()+1;i<=l;i++)
    {
        // if Z[i] (matched region) is equal to pattern
        // length we got the pattern
        if(Z[i]>=pattern.length())
        {
            sol++;
            if(sol<=1000)
                V.push_back(i-pattern.length()-1);
        }
    }
    fout<<sol<<"\n";
    for(auto j:V)
        fout<<j<<" ";
}

// Fills Z array for given string str[]
///Z[i] reprezinta cea mai lunga lungime a prefixului care incepe din i si apartine pattern-ului
void construct_Z(string S,int Z[])
{
    int l=S.length()-1;
    int st,dr,k;
    // [L,R] make a window which matches with prefix of s
    st=dr=1;
    for(int i=2;i<=l;i++)
    {
        // if i>R nothing matches so we will calculate.
        // Z[i] using naive way.
        if(i>dr)
        {
            st=i;
            dr=i;
            // R-L = 0 in starting, so it will start
            // checking from 0'th index. For example,
            // for "ababab" and i = 1, the value of R
            // remains 0 and Z[i] becomes 0. For string
            // "aaaaaa" and i = 1, Z[i] and R become 5
            while(dr<=l&&S[dr-st+1]==S[dr])
                dr++;
            dr--;
            Z[i]=dr-st+1;
        }
        else
        {
            // k = i-L so k corresponds to number which
            // matches in [L,R] interval.
            k=i-st+1;
            // if Z[k] is less than remaining interval
            // then Z[i] will be equal to Z[k].
            // For example, str = "ababab", i = 3, R = 5
            // and L = 2
            if (Z[k]<dr-i+1)
                Z[i]=Z[k];

            // For example str = "aaaaaa" and i = 2, R is 5,
            // L is 0
            else
            {
                // else start from R and check manually
                st=i;
                while(dr<=l&&S[dr-st+1]==S[dr])
                    dr++;
                dr--;
                Z[i]=dr-st+1;
            }
        }
    }
}
int main()
{
    fin>>pattern;
    fin>>text;
    solve(text,pattern);
    return 0;
}