Cod sursa(job #3124169)

Utilizator CelestinNegraru Celestin Celestin Data 27 aprilie 2023 02:36:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
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(a[i]==a[len]){
            len++;
            lps[i]=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)
       {
           nrap++;
           if(nrap<=1000)
             v.push_back(i-j);
           j=lps[j-1];
       }
   }
}
int main()
{
    f>>a>>b;
    m=strlen(a);
    n=strlen(b);
    precompute();
    kmp();
    int k=v.size();
    g<<min(1000,k)<<'\n';
    sort(v.begin(),v.end());
    for(int i=0;i<min(1000,nrap);i++)
        cout<<v[i]<<" ";
    return 0;
}