Cod sursa(job #1830820)

Utilizator calin1Serban Calin calin1 Data 17 decembrie 2016 10:33:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 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);

    for(int i = 0 , j = 1 ; j < n ; )
    {
        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++;

            }
        }

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

    int nr = 0;

    for(int i = 0 , j = 0 ; i < m ; )
    {
        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++;

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

                    vec.push_back(i - j);

                    j = a.pattern[j - 1];

                    if(i == m - 1)
                    {
                        i++;

                        break;
                    }
                }
            }
        }

        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;
}