Cod sursa(job #2718795)

Utilizator ognean.mihnea12Ognean Mihnea Ionut ognean.mihnea12 Data 9 martie 2021 10:34:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;

#define NMAX 2000005

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int i, j, lps[NMAX], len, poz, rez[NMAX], n, m;
char s[NMAX], pat[NMAX];

int main()
{
    fin>>pat;
    fin.get();
    fin>>s;
    fin.get();
    len=0;
    i=1;
    lps[0]=0;
    n=strlen(s);
    m=strlen(pat);
    while(i<m)
    {
        if(pat[i]==pat[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if(len==0)
            {
                lps[i]=0;
                i++;
            }
            else
            {
                len=lps[len-1];
            }
        }
    }
    i=0;
    j=-1;
    while(i<n)
    {
        if(s[i]==pat[j+1])
        {
            i++;
            j++;
            if(j==m-1)
            {
                poz++;
                rez[poz]=i-m;
                j=lps[j]-1;
            }
        }
        else
        {
            if(j==-1)
            {
                i++;
            }
            else
            {
                j=lps[j]-1;
            }
        }
    }
    fout<<poz<<'\n';
    for(i=1; i<=poz; i++)
        fout<<rez[i]<<" ";
    return 0;
}