Cod sursa(job #2038424)

Utilizator anisca22Ana Baltaretu anisca22 Data 13 octombrie 2017 17:47:00
Problema Potrivirea sirurilor Scor 22
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int a, b, f, cnt;
char A[NMAX], B[NMAX], S[NMAX];
vector <int> rsp;

int main()
{
    fin >> A + 1 >> B + 1;
    a = strlen(A + 1);
    b = strlen(B + 1);
    S[0] = -1;
    S[1] = 0;
    for (int i = 2; i <= a; i++)
    {
        int prv = i - 1;
        char ch = A[i];
        while (S[prv] != -1 && A[S[prv] + 1] != ch)
            prv = S[prv];
        S[i] = S[prv] + 1;
    }
    for (int i = 1; i <= b; i++)
    {
        while (f != -1)
            if (A[f + 1] == B[i])
                break;
        else f = S[f];
        if (f == -1)
            f = 0;
        else{
            f++;
            if (f == a)
            {
                rsp.push_back(i - a);
                f = S[f];
            }
        }

    }
    fout << rsp.size() << "\n";
    vector <int> :: iterator it;
    for (it = rsp.begin(); it != rsp.end(); it++)
    {
        fout << *it << " ";
    }
    return 0;
}