Cod sursa(job #2708547)

Utilizator MateGMGozner Mate MateGM Data 18 februarie 2021 21:12:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream be("strmatch.in");
ofstream ki("strmatch.out");

vector<int>build_kmp(string a)
{
    int na=a.length();
    vector<int>t(na,0);
    for(int i=1;i<na;i++)
    {
        int k=t[i-1];
        while(true)
        {
            if(a[i]==a[k])
            {
                t[i]=k+1;
                break;
            }
            else if(k==0)
            {
                t[i]=0;
                break;
            }
            else
                k=t[k-1];
        }
    }
    return t;
}

int main()
{
    string a,b;
    be>>a>>b;
    int na=a.length();
    int nb=b.length();
    auto t=build_kmp(a);
    int s=0,i=0;
    vector<int>poz;
    while(s<nb-na+1)
    {
        if(i==na)
        {
            poz.push_back(s);
            s+=i-t[i-1];
            i=t[i-1];
        }
        else if(b[s+i]==a[i]){
            i++;
        }
        else if(i==0)
            s++;
        else {
            s+=i-t[i-1];
            i=t[i-1];
        }
    }
    ki<<poz.size()<<endl;
    for(int i=0;i<poz.size() && i<1000;i++)
        ki<<poz[i]<<" ";
    return 0;
}