Cod sursa(job #2986177)

Utilizator razviOKPopan Razvan Calin razviOK Data 27 februarie 2023 21:10:10
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

/*struct Nod
{
    int value;
    struct Nod *next;
}*List;*/
char stringA[2000001],stringB[2000001];
unsigned int prefix[2000001],appereances[1000];
/*void AddToList(Nod *&List,int val)
{
    if(&List==NULL)
    {
        List->value=val;
        List->next=NULL;
    }
    else
    {
        Nod *p=new Nod;
        p->value=val;
        p->next=List;
        // p->next=NULL;

        // struct Nod *nod_current=List;

        //while(nod_current->next!=NULL)
        // nod_current=nod_current->next;

        //nod_current->next=p;

        List=p;
    }
}
void PrintList(Nod *&List)
{
    while(List!=NULL)
    {
        printf("%u ",List->value);
        List=List->next;
    }
}
*/
unsigned int Minimum(unsigned int a,unsigned int b)
{
    return (a>b) ? b:a;
}
void BuildPrefix(int length)
{
    unsigned int j=0;
    prefix[1]=0;
    for(int i=2; i<=length; i++)
    {
        while(j>0 && stringA[j+1]!=stringA[i])
            j=prefix[j];

        if(stringA[j+1]==stringA[i])
            j=j+1;

        prefix[i]=j;

    }
}
void KMP(unsigned int lengthA,unsigned int lengthB)
{
    unsigned int j=0,num_appartitons=0;
    for(unsigned int i=1; i<=lengthB; i++)
    {
        while(j>0 && stringA[j+1]!=stringB[i])
            j=prefix[j];


        if(stringA[j+1]==stringB[i])
            j=j+1;


        if(j==lengthA)
        {
            num_appartitons++;

            if(num_appartitons<1000)
                appereances[num_appartitons-1]=i-j+1;

            j=prefix[j];
        }


    }

    printf("%u\n",num_appartitons);
    //PrintList(List);
    for(unsigned int i=0; i<Minimum(1000,num_appartitons); i++)
        printf("%u ",appereances[i]);
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s",stringA+1);
    scanf("%s",stringB);

    unsigned int lengthA=strlen(stringA+1);
    unsigned int lengthB=strlen(stringB+1);


    // stringA[lengthA+1]='\0';
    // stringB[lengthB+1]='\0';
    //strcpy(stringA+1,stringA);
    //strcpy(stringB+1,stringB);
    // stringA[0]=' ';
    // stringB[0]=' ';
    BuildPrefix(lengthA);
    KMP(lengthA,lengthB);

    return 0;
}