Cod sursa(job #2364023)

Utilizator ZheroAlexandru Culea Zhero Data 3 martie 2019 20:13:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
//Algoritmul KMP
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;

#define LMax 2000001
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[LMax],B[LMax];
int v[LMax],sol[LMax];
int minim(int x,int y)
{
    if(x<y)
        return x;
    return y;
}
void citire()
{
    f.getline(A,LMax-2);
    f.getline(B,LMax-2);
    f.close();
}
void prefix(int n)
{
    v[0]=0;
    int i=1,j=0;
    while(i<=n)
    {
        if(A[j]==A[i])
        {
            v[i]=j+1;
            i++; j++;
        }
        else if(j>0)
            j=v[j-1];
        else
        {
            v[i]=0;
            i++;
        }
    }
}
void solutie()
{
   int l1,l2,j=0,i=0;
   short int contor=0;
   l1=strlen(A);
   l2=strlen(B);
   prefix(l1-1);
   while(i<l2)
   {
        if(B[i]==A[j])
            if(j==l1-1)
            {
                sol[++contor]=i-l1+1;
                if(contor==1000)
                    break;
                j=v[j-1];
            }
            else
            {
                i++;
                j++;
            }
        else if(j>0)
            j=v[j-1];
        else
            i++;
   }
   g<<contor<<'\n';
   for(short int i=1;i<=minim(contor,1000);i++)
        g<<sol[i]<<" ";
    g.close();
}
int main()
{
    citire();
    solutie();
    return 0;
}