Cod sursa(job #2418464)

Utilizator RK_05Ivancu Andreea Raluca RK_05 Data 5 mai 2019 02:01:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define nmax 2000005

using namespace std;

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

char a[nmax], b[nmax];
int v[nmax], sol[nmax], ok, n, la, lb;

void kmp(){
    int i = 0, j = 0;
    while(i < lb){
        if(b[i] == a[j]){
            if(j == (la - 1)){
                sol[n++] = i - la + 1;
                if(n == 1001)
                    return;
//                ++i;
                j = v[j - 1];
            }
            else{
                i++;
                j++;
            }
        }
        else{
            if(j == 0)
                i++;
            else
                j = v[j - 1];
        }
    }
}

void prefix(){
    int i = 1, j = 0;
    while(i < lb){
        if(a[i] == a[j]){
            v[i] = j + 1;
            ++i; ++j;
        }
        else{
            ok = 0;
            while(ok == 0){
                j = v[j - 1];
                if(a[i] == a[j]){
                    v[i] = j + 1;
                    ++i; ++j;
                    ok = 1;
                }
                else if(j == 0){
                    v[i] = 0;
                    ok = 1;
                    ++i;
                }
            }
        }
    }
}

int main(){

    fin.getline(a, 20000000);
    fin.getline(b, 20000000);
    la = strlen(a);
    lb = strlen(b);
    prefix();
    kmp();
    fout << n << '\n';
    for(int i = 0; i < n; ++i)
        fout << sol[i] << " ";
    fin.close();
    fout.close();
    return 0;
}