Cod sursa(job #2675225)

Utilizator gafton13andreeaGafton Andreea gafton13andreea Data 21 noiembrie 2020 11:28:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
char pattern[20000], text[20000],*p;
int lps[1000],len,n,nr,v[10000];

void LPS()
{
     n=strlen(pattern);
lps[0]=0;
int i=1;
  while(i<n)
  {
      if(pattern[i]==pattern[len])
      {
      len++;
      lps[i]=len;
      i++;
      }
      else
          if(len!=0)
        len=lps[len-1];
        else
            lps[i++]=0;
  }
}

int main()
{
   freopen("strmatch.in", "r", stdin);
   ofstream g("strmatch.out");
  scanf("%s\n%s", &pattern, &text);
  int i=0,j=0;
  int m=strlen(text);
  LPS();
  while(i<m)
  {
     if(text[i]==pattern[j])
        i++,j++;
     else
     if(j!=0)
        j=lps[j-1];
     else
        i++;
     if(j==n)
     {
        v[nr++]=i-j;
         j=lps[j-1];
     }

  }
  g<<nr<<'\n';
  for(int i=0;i<nr;++i)
    g<<v[i]<<' ';
    return 0;
}