QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#515205	#2273. Suffixes may Contain Prefixes	WorldFinalEscaped^#	AC ✓	221ms	86652kb	C++17	2.6kb	2024-08-11 15:58:42	2024-08-11 15:58:42

Judging History

你现在查看的是最新测评结果

[2024-08-11 15:58:42]
评测

测评结果：AC
用时：221ms
内存：86652kb

查看

[2024-08-11 15:58:42]
提交

answer

#include <bits/stdc++.h>

#include <random>

using namespace std;

const int SIZE = 2000 + 5;

typedef long long ll;

const ll INF = 1e18;
const ll MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
const ll BASE1 = 233, BASE2 = 114514;

int n;
char li[SIZE];
int len;

int fail[SIZE], nxt[SIZE][26];
ll cred[SIZE][26];
ll dp[SIZE][SIZE];
ll h1[SIZE][SIZE], h2[SIZE][SIZE];

int main(void) {
    scanf("%s%d", li + 1, &len);
    n = strlen(li + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            h1[i][j] = (h1[i][j - 1] * BASE1 + li[j] - 'a' + 1) % MOD1;
            h2[i][j] = (h2[i][j - 1] * BASE2 + li[j] - 'a' + 1) % MOD2;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 26; ++j) {
            if (li[i] - 'a' == j) {
                fail[i] = nxt[fail[i - 1]][j];
                nxt[i - 1][j] = i;
            } else {
                nxt[i - 1][j] = nxt[fail[i - 1]][j];
            }
        }
    }
    for (int j = 0; j < 26; ++j) {
        nxt[n][j] = nxt[fail[n]][j];
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < 26; ++j) {
            for (int k = 1; k <= i; ++k) {
                // [k..i] + j == [1..i-k+2]
                ll t1 = (h1[k][i] * BASE1 + j + 1) % MOD1;
                ll t2 = (h2[k][i] * BASE2 + j + 1) % MOD2;
                if (t1 == h1[1][i - k + 2] && t2 == h2[1][i - k + 2]) {
                    ++cred[i][j];
                }
            }
            if (j == li[1] - 'a') {
                ++cred[i][j];
            }
        }
    }
    // for (int i = 1; i <= n; ++i) {
    //     for (int j = 0; j < 26; ++j) {
    //         if (nxt[i][j]) {
    //             printf("nxt[%d][%d] = %d\n", i, j, nxt[i][j]);
    //         }
    //     }
    // }

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = -INF;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (dp[i][j] >= 0) {
                for (int k = 0; k < 26; ++k) {
                    dp[i + 1][nxt[j][k]] =
                        max(dp[i + 1][nxt[j][k]], dp[i][j] + cred[j][k]);
                }
            }
        }
    }
    // for (int i = 0; i <= len; ++i) {
    //     for (int j = 0; j <= n; ++j) {
    //         if (dp[i][j] >= 0) {
    //             printf("dp[%d][%d] = %lld\n", i, j, dp[i][j]);
    //         }
    //     }
    // }
    ll ans = *max_element(dp[len], dp[len] + n + 1);
    printf("%lld\n", ans);
    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 20ms

memory: 33228kb

input:

fsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfsfsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfsfsfffsfffssfsfffsfsf...

output:

result:

ok single line: '852'

Test #2:

score: 0

Accepted

time: 50ms

memory: 32268kb

input:

ddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttdddddttddttddttddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttddddddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttdddddttddttddttddttddttddttddddtdddttddttddttdddddttddttddt...

output:

result:

ok single line: '5894'

Test #3:

score: 0

Accepted

time: 206ms

memory: 86652kb

input:

wswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswwswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswssswwswwswswwwswswswwwsswswswwwswswswwwswswsswswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswwswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswssswwswwswswwwswsws...

output:

result:

ok single line: '10500'

Test #4:

score: 0

Accepted

time: 25ms

memory: 25252kb

input:

sjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsjssjsspffsjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsjssjssjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsj...

output:

result:

ok single line: '4267'

Test #5:

score: 0

Accepted

time: 204ms

memory: 85588kb

input:

mmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmpmmpmmmppmmpmmmpmmpmpfmzmmpmmmmmpmmmmmpmmmmpmmmpmmpmpfmzmmpmmmmmpfqmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmpmmpmmmppmmpmmmpmmpmpfmzmmpmmmmmpmmmmmpmmmmpmmmpmmpmpfmzmmpmmmmmpfqmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpm...

output:

result:

ok single line: '9536'

Test #6:

score: 0

Accepted

time: 27ms

memory: 24408kb

input:

pepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepyzpepypopepepypgakpepypopepepypopepypopepepyzpepypopepepypepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepypopepepypopepypopepvplpepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepyzpepypopepep...

output:

result:

ok single line: '4033'

Test #7:

score: 0

Accepted

time: 202ms

memory: 85592kb

input:

fifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfiffifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfyqnfifuurfifuugfifuurfifufifuurfifuugfifuurxvfifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfiffifuurfifuu...

output:

result:

ok single line: '9452'

Test #8:

score: 0

Accepted

time: 24ms

memory: 19640kb

input:

gwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgxlggwcgwgxrgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgwvgwgxlggwgxihdggw...

output:

result:

ok single line: '3584'

Test #9:

score: 0

Accepted

time: 1ms

memory: 5908kb

input:

aabaacaabaa
101

output:

result:

ok single line: '249'

Test #10:

score: 0

Accepted

time: 1ms

memory: 6100kb

input:

aabaacaabaa
102

output:

result:

ok single line: '251'

Test #11:

score: 0

Accepted

time: 1ms

memory: 8068kb

input:

aabaacaabaa
103

output:

result:

ok single line: '253'

Test #12:

score: 0

Accepted

time: 1ms

memory: 6016kb

input:

aabaacaabaa
104

output:

result:

ok single line: '255'

Test #13:

score: 0

Accepted

time: 1ms

memory: 8248kb

input:

aabaacaabaa
105

output:

result:

ok single line: '257'

Test #14:

score: 0

Accepted

time: 0ms

memory: 15620kb

input:

cciccpccicc
2000

output:

result:

ok single line: '4995'

Test #15:

score: 0

Accepted

time: 0ms

memory: 13492kb

input:

lkultxuuxtkltukllulxkltuutkuuttkuxutuuxuutuxtkxktklltllulkltxtttkkkxxtuxltkxtxtttlltttlkkkutkkuxulklxuuxullkkxtktlxtutuxlktkkllxutlllxkltkutxltxtlluxxlxxxklxlluuxllllxxlllluktkxtkutluktxkkukluktkkuktlkkultukulxlxkltlllkkluluutkxlxkuktktxxtkkkkkuxtxttkxtuxkkttklltulktltxkutluuulluxtuxlllltlutxulxxltk...

output:

result:

ok single line: '1'

Test #16:

score: 0

Accepted

time: 8ms

memory: 16680kb

input:

zrszgeggmmagjcibhsuuugohqppnncuuksrynidfbmhaqpnzswblenhttvtgadwjybijjwhixqppgzqajdqbmjrgaziljastkonutvyqrxtvshhoidkixodyrekyshlafxnikbgaqegxbgwmpgbxnpkdxhnhcocmbpimftogrlydyqitekbfvtimiztujfejkomujzztadjhrvdqlakxnbctuaubumwlwyibmyjabrrdznkvndghplgqjmcvqhmgbsrnpmjjbkkqmnvzczlpsrgdmsmmcgksbkhzatnpiwch...

output:

result:

ok single line: '2'

Test #17:

score: 0

Accepted

time: 3ms

memory: 15768kb

input:

xxiiixxhhhxxiiixx
1996

output:

result:

ok single line: '4187'

Test #18:

score: 0

Accepted

time: 0ms

memory: 13944kb

input:

xxiiixxhhhxxiiixx
1997

output:

result:

ok single line: '4190'

Test #19:

score: 0

Accepted

time: 0ms

memory: 15592kb

input:

xxiiixxhhhxxiiixx
1998

output:

result:

ok single line: '4192'

Test #20:

score: 0

Accepted

time: 3ms

memory: 14280kb

input:

xxiiixxhhhxxiiixx
1999

output:

result:

ok single line: '4194'

Test #21:

score: 0

Accepted

time: 6ms

memory: 13912kb

input:

xxiiixxhhhxxiiixx
2000

output:

result:

ok single line: '4196'

Test #22:

score: 0

Accepted

time: 4ms

memory: 14164kb

input:

xxiiixxhhhxxiiixxicpcicpc
2000

output:

result:

ok single line: '4196'

Test #23:

score: 0

Accepted

time: 1ms

memory: 6432kb

input:

c
123

output:

result:

ok single line: '123'

Test #24:

score: 0

Accepted

time: 0ms

memory: 13704kb

input:

p
2000

output:

result:

ok single line: '2000'

Test #25:

score: 0

Accepted

time: 8ms

memory: 13172kb

input:

nananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananana
500

output:

result:

ok single line: '40100'

Test #26:

score: 0

Accepted

time: 109ms

memory: 84504kb

input:

czgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczg...

output:

result:

ok single line: '1717'

Test #27:

score: 0

Accepted

time: 220ms

memory: 86460kb

input:

fjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxx...

output:

result:

ok single line: '201000'

Test #28:

score: 0

Accepted

time: 209ms

memory: 86124kb

input:

uuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxpp...

output:

result:

ok single line: '134469'

Test #29:

score: 0

Accepted

time: 42ms

memory: 29836kb

input:

ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

result:

ok single line: '440469'

Test #30:

score: 0

Accepted

time: 221ms

memory: 86424kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

result:

ok single line: '2001000'

Test #31:

score: 0

Accepted

time: 1ms

memory: 7908kb

input:

a
1

output:

result:

ok single line: '1'

Test #32:

score: 0

Accepted

time: 1ms

memory: 7980kb

input:

z
1

output:

result:

ok single line: '1'

Test #33:

score: 0

Accepted

time: 0ms

memory: 5880kb

input:

cc
1

output:

result:

ok single line: '1'

Test #34:

score: 0

Accepted

time: 1ms

memory: 5868kb

input:

gg
1

output:

result:

ok single line: '1'

Test #35:

score: 0

Accepted

time: 1ms

memory: 5948kb

input:

yx
2

output:

result:

ok single line: '2'

Test #36:

score: 0

Accepted

time: 1ms

memory: 5964kb

input:

tr
2

output:

result:

ok single line: '2'

Test #37:

score: 0

Accepted

time: 1ms

memory: 6068kb

input:

xxyxxyx
20

output:

result:

ok single line: '49'