Cod sursa(job #2690769)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 25 decembrie 2020 17:34:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
//#pragma GCC optimize ("03")
#define FastIO ios_base::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define FILES freopen("strmatch.in" , "r" , stdin) , freopen("strmatch.out" , "w" , stdout)

using namespace std;

const int N = 2e6 + 10;

int a[2 * N];
string A , B;
vector < int > start;

signed main()
{
	#ifndef ONLINE_JUDGE
		FastIO , FILES;
	#endif

    cin >> A;
    cin >> B;

    int ans = 0 , M = A.size();

    A += "#" + B;

    for(int i = 1 ; i < A.size() ; i++)
    {
        int j = a[i - 1];

        while(j && A[j] != A[i])
            j = a[j - 1];

        a[i] = j + (A[j] == A[i]);

        if(a[i] == M)
            start.push_back(i - M + 1);
    }

    cout << start.size() << '\n';

    for(int i = 0 ; i < min(1000 , (int)start.size()) ; i++)
        cout << start[i] - M - 1 << ' ';

    return 0;
}