Cod sursa(job #3124260)

Utilizator proflaurianPanaete Adrian proflaurian Data 27 aprilie 2023 16:01:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.89 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N = 4000010;
char s[N];
int n,m,Z[N],R,L,P,cnt;
vector<int> poz;
int main()
{
    string A;
    f>>A;
    m=A.size();
    strcpy(s,A.c_str());
    s[m]='$';
    f>>A;
    strcat(s,A.c_str());
    n=strlen(s);
    for(int i=1; i<n; i++)
    {
        /// calculam functia z[] pentru toate pozitiile
        /// cazul 1-suntem in afara box-ului
        /// refacem complet box-ul incepand din L=i ( brut )
        if(i>R)
        {
            L=R=i;
            P=0;
            while(s[P]==s[R])
            {
                P++;
                R++;
            }
            Z[i]=P;
            R--;
        }
        /// Pozitia i este in interiorul box-ului [L,R]
        else
        {
            int k=i-L; /// k = pozitia in box a lui i ( pozitia din prefix care
            /// corespunde lui i in box)

            /// cazul 2-suntem in interiorul boxului dar la o pozitie
            /// din care prefixul se opreste strict inainte de terminarea box-ului
            /// k nu bate in afara prefixului corespunzator box-ului
            /// deci si i va bate in box exact la fel de mult ca di k in prefix>
            if(i+Z[k]-1<R)
                Z[i]=Z[k];

            /// ALTFEL
            /// cazul 3-sun in interiorul box-ului si din pozitia i pana la capatul
            /// box-ului am un prefix de s[] - aici trebuie sa verificam daca
            /// creem un box nou care incepe in i si se termina CEL PUTIN in R
            /// Resetam L in i avem deja asigurat ok pana la R
            /// dar e posibil sa putem extinde box-ul si dupa i
            /// adica este posibil sa avansam capatul R al box-ului
            else
            {
                L=i;
                R++;
                P=R-L;
                while(s[P]==s[R])
                {
                    P++;
                    R++;
                }
                R--;
                Z[i]=P;
            }
        }
        if(Z[i]==m)
        {
            cnt++;
            if(cnt<1000)
                poz.push_back(i-m-1);
        }

    }
    g<<cnt<<'\n';
    for(auto it:poz)
        g<<it<<' ';
    g<<'\n';
    return 0;
}
//
//             L           0  P
//   P                     L  R
//asdfasasdx ....    asdfasasdf????
//   P  k             [    i
//      |             0    k
//      V
//      0
//
//    din i ma pot extinde cel mult pana la pozitia R
//    dar Z[k] imi spune ca din i ma pot extinde pana la i+Z[k]-1, dar numai daca
//    i+Z[k]-1 < R
//    Ce se intampla daca i+Z[k]-1>=R. Atunci
//
//
//  k=i-L







//   >>>>>      >>>>>
//   bbbbbbbbbbbibbbbbbbbbbbbbb
//
//             /
//            /
//           /
//          /
//         /
//ppppppppkppppppppppppppppp
//>>>>>   >>>>>
//
//
//