Cod sursa(job #2204699)

Utilizator mrhammerCiocan Cosmin mrhammer Data 16 mai 2018 20:45:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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 n_a = 0;
    for(int i=0;i<strlen(b);i++)
    {
        if(j == strlen(a)-1)
        {
            if(a[j] == b[i])
            {
                n_a++;
                if(pos_holder.size() < 1000) pos_holder.push_back(i-strlen(a));
            }
            j = automaton[j];
        }
        if(a[j] == b[i]) j++;
    }
    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]+1<<" ";
    }
}