Cod sursa(job #2454386)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 8 septembrie 2019 10:46:11
Problema Potrivirea sirurilor Scor 52
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string s1, s2;
int poz = 1, ind;
int lps [2000003];
vector <int> ans;
int main (){
    fin >> s1 >> s2;
    while (poz < s1.size ()){
        if (s1 [poz] == s1 [ind])
            lps [poz ++] = ++ ind;
        else{
            if (ind)ind = lps [ind - 1];
            else lps [poz ++] = 0;
        }
    }
    poz = 0;
    while (poz < s2.size ()){
        if (s1 [ind] == s2 [poz])
            poz ++, ind ++;
        if (ind == s1.size ()){
            ans.push_back (poz - ind);
            ind = lps [ind - 1];
        }
        else if (poz < s2.size () && s1 [ind] != s2 [poz]){
            if (ind)ind = lps [ind - 1];
            else poz ++;
        }
    }
    fout << ans.size () << '\n';
    for (int poz = 0; poz < min ((int)ans.size (), 1000); poz ++)
        fout << ans [poz] << " ";
    return 0;
}