Cod sursa(job #2387712)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 25 martie 2019 09:13:30
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <cstring>
#define MAX 2000004
using namespace std;

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

int q1, q2, j, gasit, sol[MAX], pattern[MAX];
char A[MAX], B[MAX];

int main()
{
    cin.getline(A, MAX);
    cin.getline(B, MAX);

    q1 = strlen(A);
    q1--;
    q2 = strlen(B);
    q2--;

    j = 0;
    for(int i=1; i <= q1; i++)
    {
        while(A[i] != A[j] && j > 0)
        j =  A[j-1];
        if(A[i] == A[j])
        j++;

        pattern[i] = j;
    }

    j=1;
    for(int i=0; i <= q2; i++)
    {
        while(B[i] != A[j] && j > 0)
        {
            j = pattern[j-1];
        }

        if(B[i] == A[j])
        {
            j++;
        }

        if(j == q1+1)
        {
            gasit++;
            sol[gasit] = i-j+1;
        }
    }
    cout << gasit << '\n';
    for(int i=1; i <= gasit; i++)
    {
        cout << sol[i] << ' ';
    }
}