Cod sursa(job #2748955)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 4 mai 2021 13:39:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define NMAX 1009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[NMAX];
char b[NMAX];
int poza[NMAX];
int pozb[NMAX];
int lga,lgb;
vector<int> sol;
void pre()
{
    poza[0]=-1;
    int j=-1;
    int i;
    for(i=1;i<lga;i++)
    {
        while(j>=0 && a[j+1]!=a[i])
            j=poza[j];
        if(a[i]==a[j+1]) ///poate nu gasesc nimic
           j++;
        poza[i]=j;
    }

}
void kmp()
{
    int i,j;
    j=-1;
    for(i=0;i<lgb;i++)
    {
        while(  b[i]!= a[j+1] && j>=0)
             j= poza[j];
        if( b[i]== a[j+1])
           j++;
        pozb[i]=j;
        if(j==lga-1)
           sol.push_back(i-lga+1);
        
    }
}
int main()
{
 fin>>a>>b;
 int i;
 lga=strlen(a);
 lgb=strlen(b);
 pre();
 kmp();
fout<<sol.size()<<'\n';
for(i=0;i< sol.size() && i< 1000;i++  )
    fout<< sol[i]<<" ";

}