DouKaku? 5855 ocean: いくつかのデータで1秒制限を満たしてない...(情報オリンピック2007年度国内本選問題2)

Comment detail

情報オリンピック2007年度国内本選問題2 (Nested Flatten)

いくつかのデータで1秒制限を満たしてないと思いますが、とりあえず接尾辞配列で。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct char_at
{
    const char* s;

    static size_t i;

    explicit char_at(const char* s_) : s(s_) {}

    operator bool() const { return s[i]; }

    friend bool operator==(const char_at& lhs, const char_at& rhs)
    {
        return lhs.s[i] == rhs.s[i];
    }

    friend bool operator<(const char_at& lhs, const char_at& rhs)
    {
        return lhs.s[i] < rhs.s[i];
    }

    friend ostream& operator<<(ostream& out, const char_at& at) // debug
    {
        return out << (at.s + i);
    }
};

size_t char_at::i;

bool compare_s(const char_at& lhs, const char_at& rhs)
{
    return strcmp(lhs.s, rhs.s) < 0;
}

int main()
{
    string s1; getline(cin, s1);

    string s2; getline(cin, s2);

    vector<char_at> v;

    for (const char* p = s1.c_str(); *p; ++p)
    {
        v.push_back(char_at(p));
    }

    sort(v.begin(), v.end(), compare_s);

    size_t result = 0;

    for (const char* p = s2.c_str(); *p; ++p)
    {
        char_at at(p);

        pair<vector<char_at>::iterator, vector<char_at>::iterator>
            r = make_pair(v.begin(), v.end());

        for (char_at::i = 0; ; ++char_at::i)
        {
            r = equal_range(r.first, r.second, at);

            while (r.first != r.second && !*r.first)
            {
                ++r.first;
            }

            if (r.first == r.second || !at)
            {
                break;
            }
        }

        result = max(result, char_at::i);
    }

    cout << result << endl;
}

両方の文字列から接尾辞配列を作って処理するようにしたら、若干高速化しました。（手元で判定データ 2-6 が 17秒 => 10秒。このマシンはPen2-266で遅いんですが、それを差し引いても大会のマシンで1秒制限を満たすか怪しいです）

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h> // strcmp()

#define REP(i, b, e) for (size_t i = b; i < e; ++i)

bool compare_str(const char* s1, const char* s2)
{
    return strcmp(s1, s2) < 0;
}

void make_suffix_array(const std::string& s, std::vector<const char*>& v)
{
    v.resize(s.size());

    REP(i, 0, s.size())
    {
        v[i] = s.c_str() + i;
    }

    std::sort(v.begin(), v.end(), compare_str);
}

typedef std::vector<const char*>::const_iterator Iter;

void skip_empty_string(Iter& beg, Iter end, size_t depth)
{
    while (beg != end && (*beg)[depth] == '\0')
    {
        ++beg;
    }
}

void find_range(Iter& beg, Iter& end, size_t depth, char c)
{
    while (beg != end && (*beg)[depth] < c)
    {
        ++beg;
    }

    Iter cur = beg;

    while (cur != end && (*cur)[depth] == c)
    {
        ++cur;
    }

    end = cur;
}

void traverse(Iter beg1, Iter end1, Iter beg2, Iter end2, size_t depth, size_t& max_depth)
{
    skip_empty_string(beg1, end1, depth);

    skip_empty_string(beg2, end2, depth);

    while (beg1 != end1 && beg2 != end2)
    {
        const char c = (*beg1)[depth];

        Iter the_beg1 = beg1, the_end1 = end1;

        find_range(the_beg1, the_end1, depth, c);

        Iter the_beg2 = beg2, the_end2 = end2;

        find_range(the_beg2, the_end2, depth, c);

        if (the_beg1 != the_end1 && the_beg2 != the_end2)
        {
            max_depth = std::max(max_depth, depth + 1);

            traverse(the_beg1, the_end1, the_beg2, the_end2, depth + 1, max_depth);
        }

        beg1 = the_end1;

        beg2 = the_end2;
    }
}

int main()
{
    std::string s1, s2;

    std::getline(std::cin, s1);

    std::getline(std::cin, s2);

    std::vector<const char*> v1, v2;

    make_suffix_array(s1, v1);

    make_suffix_array(s2, v2);

    size_t max_depth = 0;

    traverse(v1.begin(), v1.end(), v2.begin(), v2.end(), 0, max_depth);

    std::cout << max_depth << std::endl;
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq