Cod sursa(job #2834769)

Utilizator Iulia_DianaIulia Diana Iulia_Diana Data 17 ianuarie 2022 17:22:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
vector <int> rez;
int l[2000005], n, m;
void kmp_preg()
{
    int i=1, j=1;
    while(i<n)
    {
        int k=l[i];
        while(k>0 && s1[k+1]!=s1[i+1])
            k=l[k];
        if(s1[i+1]==s1[k+1]) k++;
        l[i+1]=k;
        i++;
    }
}
void KMP()
{
    if(m<n)  return;
    int i=0, k=0;
    while(i<m)
    {
        while(k>0 && s1[k+1]!=s2[i+1])
            k=l[k];
        if(s1[k+1]==s2[i+1])  k++;
        if(k==n)
        {
             if(rez.size()<1000) rez.push_back(i-k+1);
            k=l[k];
        }
        i++;
    }
}
int main()
{
    fin >> s1 >> s2;
    n=s1.length();
    m=s2.length();
    s1=' '+s1;
    s2=' '+s2;
    kmp_preg();
    //fout << s1 << "\n" << s2;
    KMP();
    fout << rez.size() << "\n";
    for(int i=0; i<rez.size() && i<1000; i++)  fout << rez[i] << " ";
   // for(int i=1; i<=n; i++)  fout << l[i] << " ";
    return 0;
}