Cod sursa(job #1958114)

Utilizator amaliarebAmalia Rebegea amaliareb Data 8 aprilie 2017 00:55:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,i,j,k,l,r,z[4000002],zprev,nr;
char s[4000002];

int main()
{
    f.getline(s+1,2000002);
    m=strlen(s+1);
    f.getline(s+strlen(s+1)+1,2000002);
    n=strlen(s+1);
    l=r=1;
    for(i=1;i<=n;i++)
    {
        if(i>r)
        {
            j=i;
            while(j<=n && s[j]==s[j-i+1]) j++, z[i]++;
            l=i; r=j-1;
        }
        else
        {
            zprev=z[i-l+1];
            if(zprev>=r-i+1)
            {
                z[i]=r-i+1;
                j=r+1;
                while(j<=n && s[j]==s[j-i+1]) j++, z[i]++;
                r=j-1; l=i;
            }
            else
            {
                z[i]=zprev;
            }
        }
    }
    for(i=m+1;i<=n;i++) if(z[i]>=m) nr++;
    g<<nr<<'\n';
    if(nr>1000) nr=1000;
    for(i=m+1;i<=n && nr;i++)
    {
        if(z[i]>=m) g<<i-m-1<<' ', nr--;
    }
    return 0;
}