Cod sursa(job #2438299)

Utilizator Gabi395Tertelici Gabriel Gabi395 Data 12 iulie 2019 10:02:37
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[100001],s2[100001];
int main()
{
    int n=1,m=1,i,k,poz,s=0;
    f>>s2+1>>s1+1;
    int l[m+1],aux[1001],j=0;
    while(s1[n]!=0)
    {
        n++;
    }
    while(s2[m]!=0)
    {
        m++;
    }
    n--;
    m--;
    if(m>n)
    {
        g<<"0";
        return 0;
    }
    /*Prefix*/
    l[1]=0;
    for(poz=2;poz<=m;poz++)
    {
        k=l[poz-1];
        while((k>0)&&(s2[k+1]!=s2[poz]))
        {
            k=l[k];
        }
        if(s2[k+1]==s2[poz])
        {
            k=k+1;
        }
        l[poz]=k;
    }
    /*KMP*/
    k=0;
    for(poz=1;poz<=n;poz++)
    {
        while((k>0)&&(s2[k+1]!=s1[poz]))
        {
            k=l[k];
        }
        if(s2[k+1]==s1[poz])
        {
            k++;
        }
        if(k==m)
        {
            j++;
            if(j>1000)
            {
                poz=n;
            }
            else
            {
                aux[j]=poz-k;
                k=l[k];
            }
        }
    }
    g<<j<<"\n";
    for(i=1;i<=j;i++)
    {
        g<<aux[i]<<" ";
    }
    return 0;
}