Cod sursa(job #2005968)

Utilizator SCatalinStanciu Catalin SCatalin Data 28 iulie 2017 15:32:19
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <cstring>

using namespace std;

const int NMAX = 2000005;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

char A[NMAX],B[NMAX];
int prefix[NMAX],poz[1005];

int main()
{
    in.getline(A,NMAX);
    in.getline(B,NMAX);
    int LengthA = strlen(A),LengthB = strlen(B);
    int i,j=0;
    for (i = 1; i<LengthA;)
    {
        if (A[i] == A[j])
        {
            prefix[i]+=j+1;
            j++;
            i++;
        }
        else
        {
            if (j != 0)
                j = prefix[j-1];
            else
            {
                prefix[i] = 0;
                i++;
            }
        }
    }
    j = 0;
    int pz = 0,k=0;
    for (i = 0; i<LengthB;)
    {
        if (B[i] == A[j])
        {
            i++;
            j++;
        }
        else
        {
            if (j != 0)
                j = prefix[j-1];
            else
            {
                j = 0;
                i++;
            }
            pz = i;
        }
        if (j == LengthA && k<=1000)
        {
            poz[k++] = pz;
            j = 0;
            i--;
            pz = i;
        }
    }
    out << k << "\n";
    for (i = 0; i<k; i++)
        out << poz[i] << " ";
}