Cod sursa(job #1965822)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 14 aprilie 2017 17:10:27
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 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+1);
    n=strlen(s+1);
    scanf("%s",s1+1);
    m=strlen(s1+1);
    strcat(s+1,s1+1);
   // printf("%s\n",s+1);
    for(int i=2;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[1+z[i]]) z[i]++;
            if(dr<i+z[i]-1)
            {
                dr=i+z[i]-1;
                st=i;
            }
    }
    for(int i=n+1;i<=n+m;i++)
        if(z[i]==n) sol.push_back(i-n-1);
    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;
}