Cod sursa(job #1830989)

Utilizator DanyBvGeorge-Daniel Gagiu DanyBv Data 17 decembrie 2016 12:03:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define NMAX 2000005

using namespace std;

char A[NMAX], B[NMAX];
int P[NMAX], N;
vector<int> R;

void read()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n", A + 1);
    scanf("%s"  , B + 1);
    A[0] = ' ';
    B[0] = ' ';
}

void patternArray()
{
    int len_A = strlen(A);
    P[1] = 0;
    for(int i = 1, j = 2; i < len_A && j < len_A; i++)
    {
        if(A[i] == A[j])
        {
            P[i] = P[i - 1] + 1;
            j++;
        }
        else
        {
            while(j != 1)
            {
                if(A[j] == A[i])
                {
                    P[i] = j;
                    j++;
                    break;
                }
                else
                {
                    j = P[j - 1] + 1;
                }
            }
            if(j == 1)
            {
                P[i] = 0;
            }
        }
    }
}

void KMP()
{
    int len_A = strlen(A);
    int len_B = strlen(B);
    int i = 1, j = 1;
    while(i < len_B)
    {
        if(B[i] == A[j])
        {
            if(j == len_A - 1)
            {
                j = P[j - 1] + 1;
                R.push_back(i - len_A + 1);
            }
            i++;
            j++;
        }
        else
        {
            j = P[j - 1] + 1;
            i++;
        }
    }
}

void print()
{
    int len_R = min((int)R.size(), 1000);
    printf("%d\n", len_R);
    for(int i = 0; i < len_R; i++)
        printf("%d ", R[i]);
}

int main()
{
    read();
    patternArray();
    KMP();
    print();
    return 0;
}