Cod sursa(job #2847119)

Utilizator Emilia23Dobra Emilia Emilia23 Data 10 februarie 2022 11:50:58
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int SIZE = 25;
char s1[SIZE],s2[SIZE];
int n,m,v[SIZE],cnt,sol[SIZE];

void pattern()
{
    int i,j=1;
    for(i=2;i<=n;i++)
    {
       if(s1[i]==s1[j])
       {
           v[i]=v[i-1]+1;
           j++;
       }
       else
       {
           v[i]=0;
           j=1;
       }
    }

    //for(i=1;i<=n;i++)g<<v[i]<<' ';
}

void kmp()
{
    int i,j=0;
    for(i=1;i<=m;i++)
    {
        if(cnt==3)
        {
            cnt++;
            cnt--;
        }
        if(s2[i]==s1[j+1])
        {
            j++;
            if(j==n)
            {
              cnt++;
              sol[cnt]=i-n;
              j=v[j];
            }
        }
        else
        {
            j=1;
        }
    }
    g<<cnt<<'\n';
    for(i=1;i<=cnt;i++)g<<sol[i]<<' ';
}

int main()
{
    s1[0]=' ';
    s2[0]=' ';
    f.getline(s1+1,SIZE);
    f.getline(s2+1,SIZE);
    n=strlen(s1)-1;
    m=strlen(s2)-1;
    pattern();
    kmp();
    return 0;
}