Cod sursa(job #3236461)

Utilizator bobot1Aldoiu Sebastian Alexandru bobot1 Data 28 iunie 2024 19:15:33
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int o, vct[2000005];

void calclps(char* pat, int m, int* lps);

void kmp(char* pat, char* txt)
{
    int m=strlen(pat);
    int n=strlen(txt);
    int lps[m];

    calclps(pat, m, lps);

    int i=0;
    int j=0;
    while((n-i)>=(m-j))
    {
        if(pat[j]==txt[i])
        {
            i++;
            j++;
        }
        if(j==m)
        {
            o++;
            vct[o]=i-j;
            j=lps[j-1];
            if(o==1000) return 0;
        }
        else if(i<n && pat[j]!=txt[i])
        {
            if(j!=0)
            {
                j=lps[j-1];
            }
            else i++;
        }
    }
}
void calclps(char* pat, int m, int* lps)
{
    int len=0;
    lps[0]=0;
    int i=1;
    while(i<m)
    {
        if(pat[i]==pat[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if(len!=0)
            {
                len=lps[len-1];
            }
            else
            {
                lps[i]=0;
                i++;
            }
        }
    }
}
char txt[2000005], pat[2000005];
int main()
{
    fin>>pat;
    fin>>txt;
    kmp(pat, txt);
    fout<<o<<'\n';
    for(int i=1; i<=o; i++)
        fout<<vct[i]<<' ';
    return 0;
}