ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1684. Jack's Last Word

Output Limit Exceeded
Posted by AlexDevyatov 9 Jul 2014 23:08
Why OLE 24?

#pragma comment(linker, "/STACK:64777216")
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string>
#include<sstream>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<memory.h>
#include<ctime>
#include<cassert>

#define pb push_back
#define sz(a) (int)a.size()
#define bs binary_search
#define np next_permutation
#define mp make_pair
#define all(a) a.begin(),a.end()
#define read(a) scanf("%d", &a)
#define writeln(a) printf("%d\n", a);
#define forn(i, n) for (int i = 0; i < n; ++i)
#define forv(i, v) for (int i = 0; i < sz(v); ++i)
#define _(a, b) memset(a, b, sizeof a)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

template<class T> inline T sqr(T x) { return x * x; }

const double pi = acos(-1.0), eps = 1e-18;
const int INF = 1000 * 1000 * 1000, MAXN = 100005, MOD = INF + 7;

string s, t, ls, ans = "";
int kmp[75000 * 2 + 5];
vector<int> pos;

char al[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};

void prepare(string s) {
#ifdef _DEBUG
   freopen("input.txt", "r", stdin);
   freopen("output.txt","w",stdout);
#else
   if (sz(s) != 0) {
       freopen((s + ".in").c_str(), "r", stdin);
       freopen((s + ".out").c_str(), "w", stdout);
   }
#endif
}

void gen () {
    srand(time(NULL));
    string TMP = "";
    forn (i, 70000) {
        int k = rand() % 8;
        cout << al[k];
        TMP += al[k];
    }
    cout << '\n';
    cout << TMP;
}

void solve()
{
    cin >> s >> t;
    ls = s + "*" + t;
    kmp[0] = 0;
    for (int i = 1; i < sz(ls); i++) {
        int k = kmp[i-1];
        while (k > 0 &&  ls[i] != ls[k]) {
            k = kmp[k-1];
        }
        if (ls[i] == ls[k])
            ++k;
        kmp[i] = k;
    }
    for (int i = sz(s) + 1; i < sz(ls); i++) {
        if (kmp[i] == 0) {
            cout << "Yes";
            return;
        }
        if (i != sz(s) + 1 && kmp[i] <= kmp[i-1])
            pos.pb(kmp[i - kmp[i]]);
    }
    pos.pb(kmp[sz(ls)-1]);
    cout << "No\n";
    string tmp = "";
    int cnt = 0;
    forn (i, sz(pos)) {
        bool f = false;
        cnt += pos[i];
        forn (j, pos[i]) {
            cout << s[j];
            f = true;
        }
        if (i != sz(pos) - 1 && pos[i])
            cout << " ";
    }
}

int main()
{
   prepare("");

   //gen();
   solve();

   return 0;
}

Edited by author 09.07.2014 23:18