Cod sursa(job #1830796)

Utilizator gabor.vlad13lil pump gabor.vlad13 Data 17 decembrie 2016 10:12:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 2000005
using namespace std;

char pattern[MAX];
int indPattern[MAX];
char text[MAX];
int sol[MAX];
int nr, l;

void buildPattern()
{
    int i=1, j=0;
    indPattern[0] = 0;
    while(indPattern[strlen(pattern)-1] == -1 && i < strlen(pattern))
    {
        if (pattern[i] != pattern[j])
        {
            j = indPattern[j-1];
            if (j == 0 && pattern[i] != pattern[j])
                i++;
        }
        else
            indPattern[i] = j+1, i++, j++;
    }

    for (int i=0; i<strlen(pattern); i++)
        if (indPattern[i] == -1)
            indPattern[i] = 0;
    //for (int i=0; i<strlen(pattern); i++)
        //cout<<indPattern[i];
}

void solve()
{
    int i=0, j = 0;
    while(i < strlen(text))
    {
        if (j == strlen(pattern) - 1 && pattern[j] == text[i])
            sol[l++] = i - strlen(pattern) + 1;
        if (text[i] == pattern[j])
            i++, j++;
        else
        {
            j = indPattern[j-1];
            if (j == 0 && text[i] != pattern[j])
                i++;
        }
    }
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    memset(indPattern, -1, sizeof(indPattern));
    gets(pattern);
    gets(text);
    buildPattern();
    solve();
    printf("%d\n", l);
    if (l > 1000)
        l = 1000;
    for (int i=0; i<l; i++)
        printf("%d ", sol[i]);
    return 0;
}