Cod sursa(job #1965866)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 14 aprilie 2017 17:57:40
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
/**
    Z-Algorithm
*/
#include<bits/stdc++.h>
#define maxN 4000005
using namespace std;
char s[maxN],s1[maxN];
int n,m,st,dr,z[maxN],j;
vector<int> sol;
vector<int>::iterator it;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",s);
    scanf("\n");
    n=strlen(s);
    scanf("%s",s1);
    m=strlen(s1);
    strcat(s+1,s1);
   // printf("%s\n",s+1);
   st=-1;
   dr=-1;
    for(int i=1;i<(n+m);i++)
    {
        if(dr>=i)  z[i]=min(z[i-st+1],dr-i+1);
            while((i+z[i])<(n+m) && s[i+z[i]]==s[z[i]]) z[i]++;
            if(dr<i+z[i]-1)
            {
                dr=i+z[i]-1;
                st=i;
            }
    }
    for(int i=n;i<=n+m;i++)
        if(z[i]==n) sol.push_back(i-n);
    printf("%d\n",sol.size());
    sort(sol.begin(),sol.end());
    int sz=sol.size();
    int x=min(1000,sz);
    for(int i=0;i<x;i++)
        printf("%d ",sol[i]);

    return 0;
}