Cod sursa(job #1830835)

Utilizator calin1Serban Calin calin1 Data 17 decembrie 2016 10:46:33
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define N 2000005

using namespace std;

struct elem
{
    char sir[N];
    int pattern[N];

}a;

char b[N];

vector <int> vec;

void afisare()
{
    int l = vec.size();

    for(int i = 0 ; i < l && i < 1000; ++i)
    {
        printf("%d ",vec[i]);
    }
}

void creare()
{
    int n = strlen(a.sir);

    bool ok;

    for(int i = 0 , j = 1 ; j < n ; )
    {
        ok = true;

        if(a.sir[i] == a.sir[j])
        {
            a.pattern[j] = i + 1;

            i++;
            j++;

            continue;
        }

        while(i)
        {
            i = a.pattern[i - 1];

            if(a.sir[i] == a.sir[j])
            {
                a.pattern[j] = i + 1;

                i++;
                j++;

                ok = false;

                break;
            }
        }

        if(ok)
        {
            j++;
        }
    }
}
void comparare()
{
    int m = strlen(b);
    int n = strlen(a.sir);

    int nr = 0;

    bool ok;

    for(int i = 0 , j = 0 ; i < m ; )
    {
        ok = true;

        if(j == n)
        {
            nr++;

            vec.push_back(i - j);

            j = a.pattern[j - 1];

            if(i == m - 1)
            {
                break;
            }
        }

        if(a.sir[j] == b[i])
        {
            i++;
            j++;

            continue;
        }

        while(j)
        {
            j = a.pattern[j - 1];

            if(a.sir[j] == b[i])
            {
                i++;
                j++;

                ok = false;

                break;
            }
        }

        if(ok)
        {
            i++;
        }
    }

    printf("%d\n",nr);

    afisare();
}

void citire()
{
    gets(a.sir);

    gets(b);

    creare();

    comparare();
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    citire();

    return 0;
}