Cod sursa(job #3195434)

Utilizator MorariuTMorariu MorariuT Data 20 ianuarie 2024 19:27:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <algorithm>
#include <bitset>
#include <cstdio> 
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits.h>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector> 

using namespace std;
 
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl '\n'
 
void debug(vector<int> v)
{
    for(int i = 0;i < (int)v.size();i++) {cout << v[i] << ' ';}
    cout << endl;
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


signed main()
{
    string a, b; fin >> a >> b;

    a += "#";
    a += b;

    //cout << a << endl;

    int sz_init = a.size() - b.size() - 1;

    int n = a.size();


    vector<int> kmp(n, 0);
    vector<int> ans_pos;

    int it = 0;
    int ans = 0;
    for(int i = 1;i < n;i++)
    {
        while(it > 0 and a[it] != a[i])
        {
            it = kmp[it - 1];
        }

        //cout << "la pos: " << i << " it: " << it << endl;
        //cout << "a[i]: " << a[i] << " a[it]: " << a[it] << endl;

        if(a[i] == a[it])
        {
            //cout << "-->>>> " << endl;
            it++;
        }
    
        kmp[i] = it;

        if(it == sz_init)
        {   
            ans_pos.push_back(i - 2 * sz_init);
            ans++;
        }

        //cout << kmp[i] << " ";
    }

    fout << ans << endl;
    for(int i = 0;i < min(1000, (int)ans_pos.size());i++) fout << ans_pos[i] << " ";

	return 0;
}