Cod sursa(job #2933951)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 5 noiembrie 2022 13:53:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;

using namespace std;

const int NMAX = 2e6 + 5;
/*******************************/
// INPUT / OUTPUT

ifstream f("strmatch.in");
ofstream g("strmatch.out");
/*******************************/
/// GLOBAL DECLARATIONS

string A, B;
int N, M;
string s;
int pi[2 * NMAX];
vector <int> sol;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> A >> B;
    N = int(A.length()), M = int(B.length());
    s = A + "#" + B;
}
///-------------------------------------
inline void Solution()
{
    int j;
    for (int i = 1 ; i < s.length() ; ++ i)
    {
        j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j ++;
        pi[i] = j;
        if (pi[i] == N)
        {
            sol.push_back(i - 2 * N);
        }
    }
}
///-------------------------------------
inline void Output()
{
    g << sol.size() << "\n";
    for (int i = 0 ; i < min(1000, int(sol.size())) ; ++ i)
    {
        g << sol[i] << " ";
    }
}
///-------------------------------------
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ReadInput();
    Solution();
    Output();
    return 0;
}