Cod sursa(job #3124154)

Utilizator CelestinNegraru Celestin Celestin Data 27 aprilie 2023 02:04:27
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
char a[2000005],b[2000005];
int lps[2000005],n,m,nrap;
vector<int> v;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void precompute()
{
    int i=1,len=0;
    while(i<m)
    {
        if(lps[i]==lps[len]){
            lps[i]=len;
            len++;
            i++;
        }
        else{
          if(len>0)
              len=lps[len-1];
          else{
              lps[i]=0;
              i++;
          }
        }
    }
}
void kmp()
{
   int i=0,j=0;
   while(i<n)
   {
       if(b[i]==a[j])
       {
           i++;
           j++;
       }
       else if(i<n&&a[j]!=b[i])
       {
           if(j!=0)
               j=lps[j-1];
           else i++;
       }
       if(j==m)
       {
           if(nrap<=1000)
               v.push_back(i-j),nrap++;
           j=lps[j-1];
       }
   }
}
int main()
{
    f>>a>>b;
    m=strlen(a);
    n=strlen(b);
    precompute();
    kmp();
    g<<v.size()<<'\n';
    for(auto a:v)
       g<<a<<" ";
    return 0;
}