Cod sursa(job #2293818)

Utilizator bogdi1bogdan bancuta bogdi1 Data 1 decembrie 2018 16:54:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
char s[4000005];
char ss[2000005];
int z[4000005];
vector <int> sol;
int main()
{   freopen("strmatch.in", "r",stdin);
    freopen("strmatch.out", "w",stdout);
    int n,nn,l,r,i;
    char c;
    c=fgetc(stdin);
    for(i=1; c!='\n'; c=fgetc(stdin),i++)
        s[i]=c;
    nn=i-1;
    s[i]='#';
    c=fgetc(stdin);
    for(++i; c!='\n' && c!=EOF; c=fgetc(stdin),i++)
        s[i]=c;
    n=i-1;
    l=r=0;
    s[0]=0;
    for(i=2; i<=n; i++){
        if(r>=i)
            z[i]=min(z[i-l+1], r-i+1);
        for(; i+z[i]<=n && s[z[i]+1]==s[i+z[i]]; z[i]++);
        if(r<z[i]+i-1){
            r=z[i]+i-1;
            l=i;
        }
    }
    for(i=nn+2; i<=n; i++)
        if(z[i]>=nn)
            sol.push_back(i);
    printf("%d\n", sol.size());
    for(i=0; i<=1000 && i<sol.size(); i++)
        printf("%d ", sol[i]-nn-2);
    return 0;
}