Cod sursa(job #2985715)

Utilizator razviOKPopan Razvan Calin razviOK Data 26 februarie 2023 21:52:25
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <string.h>
using namespace std;

struct Nod
{
    int value;
    struct Nod *next;
}*List;
char stringA[2000001],stringB[2000001];
unsigned int prefix[2000001];
void AddToList(Nod *&List,int val)
{
    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)
{
    unsigned int num=0;
    while(List!=NULL && num+1<=1000)
    {
        printf("%u ",List->value);
        List=List->next;
        num++;
    }
}
void BuildPrefix(int length)
{
    unsigned int j=0;
    prefix[1]=0;
    prefix[0]=0;
    for(int i=2; i<=length; i++)
    {
        while(j>0 && stringA[i]!=stringA[j+1])
            j=prefix[j];

        if(stringA[i]==stringA[j+1])
            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 && stringB[i]!=stringA[j+1])
            j=prefix[j];

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

        if(j==lengthA)
        {
            num_appartitons++;
            AddToList(List,i-j);
            j=prefix[lengthA];
        }
    }

    printf("%u\n",num_appartitons);
    PrintList(List);
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

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

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


    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;
}