Cod sursa(job #1938001)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 24 martie 2017 15:25:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
//strmatch cu Z-algorithm

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int N = 2000010;

char A[N],B[N],*p;
int n,m,i,j,st,dr,nr,ZT,Z[N];
vector<int> sol;
void zfunction(),pfunction();
int main()
{
    A[0]='#';p=A+1;f>>p;n=strlen(p);p[n+1]='@';
    B[0]='#';p=B+1;f>>p;m=strlen(p);p[m+1]='&';
    zfunction();pfunction();
    g<<nr<<'\n';
    for(auto it:sol)
        g<<it<<' ';
    return 0;
}
void zfunction()
{
    for(i=2; i<=n; i++)
    {
        if(i<=dr&&i+Z[i-st+1]-1<dr)
            Z[i]=Z[i-st+1];
        else if(i<=dr)
        {
            j=dr-i+1;
            st=i;
            while(A[dr+1]==A[j+1])
                dr++,j++;
            Z[i]=j;
        }
        else if(A[i]==A[1])
        {
            st=dr=i;
            j=1;
            while(A[dr+1]==A[j+1])
                dr++,j++;
            Z[i]=j;
        }

    }
}
void pfunction()
{
    //Z[1]=n;
    st=dr=0;
    for(i=1; i<=m; i++)
    {
        ZT=0;
        if(i<=dr&&i+Z[i-st+1]-1<dr)
            ZT=Z[i-st+1];
        else if(i<=dr)
        {
            j=dr-i+1;
            st=i;
            while(B[dr+1]==A[j+1]&&j<n)
                dr++,j++;
            ZT=j;
        }
        else if(B[i]==A[1])
        {
            st=dr=i;
            j=1;
            while(B[dr+1]==A[j+1]&&j<n)
                dr++,j++;
            ZT=j;
        }
        if(ZT==n)
        {
            nr++;
            if(nr<1000)
                sol.push_back(i-1);
        }
        cout<<ZT;
    }
}