Cod sursa(job #2256341)

Utilizator LucaSeriSeritan Luca LucaSeri Data 8 octombrie 2018 15:45:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define sz(x) (int)((x).size())
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > vll;
typedef vector< pii > vpii;
typedef vector< pll > vpll;

typedef long double ld;

const ll MOD = 1e9 + 7;
ll lgput(ll a, ll b, ll mod) {
    ll ret = 1;
    while( b ){
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return ret;
}

int binarySearch(vector< int > &v, int value) {
    int best = 0;
    for(int step = 29; step >= 0; --step) {
        if(best + (1<<step) < v.size() && v[best + (1<<step)] <= value) best += (1<<step);
    }

    return best;
}

inline ll inv(ll x, ll MOD) {
    return lgput(x, MOD - 2, MOD);
}

const int MAXN = 2e6 + 10;
int sol[1010];
int cnt = 0;
int pi[MAXN];

int main() {
//    freopen("input", "r", stdin); freopen("output", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(12);
    cout << fixed;

    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    string a, b;
    f >> a >> b;

    a = '#' + a;
    b = '#' + b;

    int n = sz(a);
    int m = sz(b);

    int q = 0;
    for(int i = 2; i < n; ++i) {
        while(q && a[q+1] != a[i]) q = pi[q];
        if(a[q+1] == a[i]) ++q;

        pi[i] = q;
    }

    q = 0;
    for(int i = 1; i < m; ++i) {
        while(q && a[q+1] != b[i]) q = pi[q];
        if(a[q+1] == b[i]) ++q;
        if(q == n - 1) {
            q = pi[n-1];
            ++cnt;
            if(cnt <= 1000) sol[cnt] = i - n + 1;
        }
    }

    g << cnt << '\n';
    for(int i = 1; i <= min(1000, cnt); ++i) g << sol[i] << ' ';
}