Cod sursa(job #1628012)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 3 martie 2016 20:15:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.9 kb
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;

const int N = 2001000;

struct str {
    long long nr;
    char c;
};

int n, m;
str a[2 * N], b[N], l[N];
vector<int> poz;

bool cmp(str a, str b) {
    return (a.nr == b.nr && a.c == b.c);
}

int z[2 * N];

void calcpot() {
    int i, j;

    for(i = 1; i <= n; ++i)
        l[i] = a[i];
    int nr = 0;
    for(i = 1; i <= n; ++i) {
        a[++nr] = l[i];
    }

    for(i = 1; i <= m; ++i)
        a[++nr] = b[i];

    int el, pmax = 0;

    for(i = 2; i <= nr; ++i) {

        if(i >= pmax) {

            for(j = i; cmp(a[j], a[j - i + 1]) && j <= nr; ++j);

            --j;

            z[i] = j - i + 1;

            pmax = j;
            el = i;

        }
        else {

            z[i] = min(z[i - el + 1], pmax - i + 1);

            for(j = i + z[i] - 1; cmp(a[j], a[j - i + 1]) && j <= nr; ++j);
            --j;

            z[i] = j - i + 1;

            if(j > pmax) {
                pmax = j;
                el = i;
            }
        }

        if(i > n && z[i] >= n) {
            poz.push_back(i - (n));
        }
    }


}

void calc() {
    int i, j;

    calcpot();

    int r = 0;

    cout << poz.size() << "\n";
    for(i = 0; i < poz.size(); ++i)
        cout << poz[i] - 1 << " ";

}

char s1[N], s2[N];

int main() {
    int i, j;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin >> s1;
    cin >> s2;
    n = strlen(s1);
    m = strlen(s2);

    for(i = 1; i <= n; ++i) {
        a[i].c = s1[i - 1];
    }
    for(i = 1; i <= m; ++i) {
        b[i].c = s2[i - 1];
    }

/*
    cin >> m >> n;


    for(i = 1; i <= m; ++i) {
        scanf("%I64d-%c ", &b[i].nr, &b[i].c);

        if(i > 1 && b[i].c == b[i - 1].c) {
            b[i - 1].nr += b[i].nr;
            --m;
            --i;
        }
    }

    for(i = 1; i <= n; ++i) {
        scanf("%I64d-%c ", &a[i].nr, &a[i].c);

        if(i > 1 && a[i].c == a[i - 1].c) {
            a[i - 1].nr += a[i].nr;
            --n;
            --i;
        }
    }

    if(n == 1) {

        int r = 0;

        for(i = 1; i <= m; ++i) {
            if(a[1].c == b[i].c)
                r += max(0LL, b[i].nr - a[1].nr + 1);
        }

        cout << r;

        return 0;
    }
    if(n == 2) {

        if(m == 1) {
            cout << 0;
            return 0;
        }

        int r = 0;

        for(i = 1; i < m; ++i) {
            if(a[1].c == b[i].c && a[2].c == b[i + 1].c && a[1].nr <= b[i].nr && a[2].nr <= b[i + 1].nr)
                ++r;
        }

        cout << r;

        return 0;
    }

    if(m < n) {
        cout << 0;
        return 0;
    }

*/

    calc();

    return 0;
}