Cod sursa(job #2241903)

Utilizator AnDrEeA1915Monea Andreea AnDrEeA1915 Data 17 septembrie 2018 12:29:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>

const int nmax = 2000005;

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int  n, m, v[nmax];
string A,B;
vector<int> rez;

void LPS(){
    int i = 1, j = 0;
    while(i < m){
        if(A[i] == A[j]){
            j++;
            v[i] = j;
            i++;
        }
        else{
            if(j != 0)
                j = v[j - 1];
            else{
                v[i] = 0;
                i++;
            }
        }
    }

}
void KMP(){
    int i = 0,j = 0;

    while(i < n){
        if(B[i] == A[j]){
            j++;
            i++;
            if(j == m){
                rez.push_back(i - j);
                j = v[j - 1];
            }
        }else{
            if(j != 0)
                j = v[j - 1];
            else
                i++;
        }
    }
}

int main()
{
    fin >> A >> B;
    n = B.size();
    m = A.size();

    LPS();
    KMP();

    fout << rez.size() <<endl;
    for(unsigned int i = 0; i < rez.size() && i < 1000; i++)
        fout<< rez[i] <<' ';

    return 0;
}