Cod sursa(job #3002290)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 14 martie 2023 17:16:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMAX=2e6+5;

string a;
string b;

int p[NMAX];

vector<int>v;

void kmp(int n)
{
    int i,k=0;
    for(i=1;i<n;i++)
    {
        while(a[i]!=a[k] && k>0)
            k=p[k-1];
        if(a[i]==a[k])
            k++;
        p[i]=k;
    }
}

int main()
{
    int n,m,i,j,kon=0;
    fin>>a>>b;
    n=a.size();
    m=b.size();
    kmp(n);
    int k=0;
    for(j=0;j<m;j++)
    {
        while(b[j]!=a[k] && k>0)
            k=p[k-1];
        if(b[j]==a[k])
            k++;
        if(k==n)
        {
            kon++;
            v.push_back(j-n+1);
        }
    }
    fout<<v.size()<<"\n";
    for(auto i:v)
        fout<<i<<" ";
    return 0;
}