Cod sursa(job #3259280)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 25 noiembrie 2024 17:13:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char a[2000005],b[2000005],A[2000005],B[2000005];
int n,m,sol[1005],nr,p[2000005];
int main()
{
    cin>>A;
    cin>>B;
    n=strlen(A);
    m=strlen(B);
    strcpy(a+1,A);
    strcpy(b+1,B);
    p[1]=0;
    int l=0;
    for(int i=2;i<=n;i++)
    {
        while(l!=0 && a[i]!=a[l+1])
            l=p[l];
        if(a[i]==a[l+1])
            l++;
        p[i]=l;
    }
    l=0;
    for(int i=1;i<=m;i++)
    {
        while(l!=0 && b[i]!=a[l+1])
            l=p[l];
        if(b[i]==a[l+1])
            l++;
        if(l==n)
        {
            nr++;
            if(nr<=1000)
                sol[nr]=i-l+1;
            l=p[l];///nu mai putem extinde prefixul de lungime n ci vom extinde cel mai bun prefix al sau
        }
    }
    cout<<nr<<'\n';
    if(nr>1000)
        nr=1000;
    for(int i=1;i<=nr;i++)
        cout<<sol[i]-1<<" ";
    return 0;
}
///Se dau doua siruri A si B formate din litere mici si mari ale alfabetului englez si din cifre.
///Se cere gasirea tuturor aparitiilor sirului A ca subsecventa a sirului B.
///pasul 1
///pentru sirul a vom construi p[i]=lungimea maxima a unui sufix terminat la pozitia i care e totodata si prefix
///pasul 2
///vom calcula l cel mai lung sufix terminat la pozitia i din b care e prefix in a
///daca gasesc un astfel de sufix de lungime n => avem potrivire
///https://www.youtube.com/watch?v=GTJr8OvyEVQ