Cod sursa(job #3151650)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 22 septembrie 2023 12:16:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a , b;
int lps[2000001];
signed main()
{
    cin >> a >> b;
    int sza = a.size();
    int szb = b.size();
    for(int i = 0 , j = 1 ; j < sza ;)
    {
        if(a[i]==a[j])
        {
            lps[j] = lps[j-1]+1;
            i++;
            j++;
        }
        else
        {
            if(i) i = lps[i-1];
            else j++;
        }
    }
    vector <int> ans;
    int hm = 0;
    for(int i = 0 , j = 0 ; j < szb ;)
    {
        if(a[i]==b[j])
        {
            if(i<sza-1)
            {
                j++;
                i++;
            }
            else
            {
                hm++;
                if(hm<=1000)
                {
                    ans.pb(j-sza+1);
                }
                i = lps[sza-1];
                j++;
            }
        }
        else
        {
            if(i == 0)
            {
                j++;
            }
            else i = lps[i-1];
        }
    }
    cout << ans.size() << '\n';
    for(auto &it : ans) cout << it << ' ';
    return 0;
}