Cod sursa(job #2556078)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 24 februarie 2020 17:47:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
#define NM 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,l,i,j;
int nr[1002],urm[NM];
string p,t;
void prefix(int n,string p){
  int i,j;
  urm[0]=0; j=0;
  for(i=1;i<n;i++){
    while(j>0&&p[i]!=p[j])
        j=urm[j-1];
    if(p[j]==p[i])
        j++;
    urm[i]=j;
  }
}
int main()
{
    f>>p>>t;
    n=p.size(); m=t.size();
    prefix(n,p);
    j=0; l=0;
    for(i=0;i<m;i++){
        while(j>0&&p[j]!=t[i])
            j=urm[j-1];
        if(p[j]==t[i])
            j++;
        if(j==n&&l<1000)
            nr[++l]=i-n+1;
    }
    g<<l<<'\n';
    for(i=1;i<=l;i++)
        g<<nr[i]<<' ';
    return 0;
}