제출 #252830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252830		NONAME	Savez (COCI15_savez)	C++14	0 / 120	81 ms	17400 KiB

savez

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int N = int(2e6) + 10;
const ll base = int(1e9) + 7;

ll n, power[N], pf[N], ans;
map <ll, ll> dp;

ll sum(ll x, ll y) { return (x + y) % base; }
ll mul(ll x, ll y) { return (x * y) % base; }
ll dec(ll x, ll y) { x -= y; while (x < 0) x += base; return x; }

int main() {
    fast_io;

    cin >> n;

    power[0] = 1;
    for (int i = 1; i <= int(2e6); ++i)
        power[i] = mul(power[i - 1], 29ll);

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int m = int(s.size());
        for (int j = 0; j < m; ++j)
            pf[j] = sum((j - 1 < 0 ? 0 : pf[j - 1]), mul((s[j] - 'A' + 1), power[j]));

        for (int j = 1; j <= m; ++j) {
            ll pref = mul(pf[j - 1], power[m - j]);
            ll suff = dec(pf[m - 1], (m - 1 - j < 0 ? 0 : pf[m - 1 - j]));

            //cerr << s << " " << pref << " " << suff << " " << pf[j - 1] << "\n";
            if (pref != suff || dp.find(pf[j - 1]) == dp.end())
                continue;

            ++dp[pf[j - 1]];
            ans = max(ans, dp[pf[j - 1]]);
        }

        dp[pf[m - 1]] = max(dp[pf[m - 1]], 1ll);
    }

    cout << ans << "\n";
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12