Cod sursa(job #3170488)

Utilizator vlad414141414141Vlad Ionescu vlad414141414141 Data 17 noiembrie 2023 18:35:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

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

const int NMAX = 2000041;
vector <int> p;
string s1, s2;
int len1, len2;

void read()
{
       p.push_back(0);p.push_back(0);
    fin >> s1 >> s2;
    s2 = "$" + s1 + "$" + s2;
    len2 = s2.size(); len1 = s1.size();

    for(int i = 2; i < len2; i++)
    {
        int jind=p[i-1];

        while(s2[i] != s2[jind + 1] && jind != 0)
            jind = p[jind];

        if(s2[i] == s2[jind + 1])
            jind++;
        p.push_back(jind);
    }
}

void solve()
{
      int cnt = 0;
    for(int i = 0; i < len2; ++i){
      //  cout << p[i] << s2[i] << " ";
        if(p[i] == len1)
            cnt++;
    }


    fout << cnt << "\n";

    int cnt1 = 0;
    for(int i = 0; i < len2; ++i)
    {
        if(cnt1 == 1000)
            break;

        if(p[i] == len1)
        {
            cnt1++;
            fout << i - 2 * len1 - 1 << " ";
        }
    }
}

int main()
{
    read();
    solve();


    return 0;
}