Cod sursa(job #2418462)

Utilizator RK_05Ivancu Andreea Raluca RK_05 Data 5 mai 2019 01:58:36
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 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]){
            i++;
            j++;
        }
        if(j == (la - 1)){
            sol[n++] = i - la + 1;
            j = v[j - 1];
            if(n == 1000)
                return;
        }
        else if(i < lb && a[j] != b[i]){
            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{
            if(j != 0)
                j = v[j - 1];
            else{
                v[i] = 0;
                ++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;
}