Cod sursa(job #2293776)

Utilizator bogdi1bogdan bancuta bogdi1 Data 1 decembrie 2018 16:15:19
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 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;
    scanf("%s", &s);
    n=strlen(s);
    strcpy(s+1,s);
    nn=n;
    scanf("%s", &ss);
    strcpy(s+n+2, ss);
    s[n+1]='#';
    n=strlen(s);
    l=r=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=2; i<n && sol.size()<1000; i++)
        if(z[i]==nn)
            sol.push_back(i);
    printf("%d\n", sol.size());
    for(i=0; i<sol.size(); i++)
        printf("%d ", sol[i]-nn-2);
    return 0;
}