Cod sursa(job #2204706)

Utilizator mrhammerCiocan Cosmin mrhammer Data 16 mai 2018 21:01:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
#define nmax 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[nmax],b[nmax];
int automaton[nmax];
vector<int> pos_holder;
void build_automaton()
{
    int j = 0;
    int i = 1;
    while(i<strlen(a))
    {
        if(a[i] == a[j])
        {
            automaton[i] = j+1;
            j++;
        }
        else
        {
            if(j != 0)
            {
                j = automaton[j-1];
                continue;
            }
        }
        i++;
    }
}
int kmp()
{
    int j = 0;
    int i = 0;
    int n_a = 0;
    while(i < strlen(b))
    {
        if(a[j] == b[i])
        {
            i++;
            j++;
        }
        if(j == strlen(a))
        {
            n_a++;
            if(pos_holder.size() < 1000) pos_holder.push_back(i-strlen(a));
            j = automaton[j-1];
        }
        else if(i < strlen(b) && a[j] != b[i])
        {
            if(j != 0) j = automaton[j-1];
            else i+=1;
        }
    }
    return n_a;
}
int main()
{
    fin>>a>>b;
    build_automaton();
    fout<<kmp()<<"\n";
    for(int i=0;i<pos_holder.size();i++)
    {
        fout<<pos_holder[i]<<" ";
    }
}