Cod sursa(job #1866286)

Utilizator r00t_Roman Remus r00t_ Data 2 februarie 2017 20:29:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
//kmp
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>

using namespace std;

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

string a,b;
int fa[2000010];

void calcSufInf(int n){
    int j=0;
    fa[j] = 0;
    for(int i=1;i<a.size();){
        if(a[i] == a[j]){
            fa[i] = j+1;
            i++;
            j++;
        }
        else {
            bool aux = false;
            while(j!=0){
                if(a[i]!=a[j]){
                    j = fa[j-1];
                }
                else {
                    fa[i] = j+1;
                    i++;
                    j++;
                    aux = true;
                }
            }
            if(aux == false)
                i++;
        }

    }
}

int main()
{
    vector<int>rez;
    fin>>a>>b;
    calcSufInf(a.size());
    /*for(int i=0;i<a.size();i++)
        fout<<fa[i]<<' ';*/
    int j=0;
    for(int i=0;i<b.size();){
        if(b[i] == a[j]){
            i++;
            j++;
        }
        else {
            j=fa[j-1];
        }
        if(j==0 && (a[j]!=b[i]))
            i++;
        if(j==a.size()-1 && a[j] == b[i])
            rez.push_back(i-a.size()+1);
    }

    fout<<rez.size()<<'\n';
    for(int i=0;i<rez.size();i++){
        if(i<=999)
            fout<<rez[i]<<' ';
        else break;
    }

    return 0;
}