QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#515078#2273. Suffixes may Contain PrefixesAfterlife#AC ✓230ms38524kbC++201.3kb2024-08-11 15:04:272024-08-11 15:04:28

Judging History

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

  • [2024-08-11 15:04:28]
  • 评测
  • 测评结果：AC
  • 用时：230ms
  • 内存：38524kb
查看
  • [2024-08-11 15:04:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=2e3+1e2+7;

string s;

int n;

long long f[N][N];

int tot;

queue<int> q;

int fail[N],son[N][26],sz[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    int m;
    cin>>m;
    for(int i=0;i<26;i++)
        son[0][i]=-1;
    int x=0;
    for(auto c:s)
    {
        c-='a';
        son[x][c]=++tot;
        memset(son[tot],-1,sizeof(son[tot]));
        x=son[x][c];
        sz[x]++;
    }
    for(int i=0;i<26;i++)
        if(son[0][i]==-1)
            son[0][i]=0;
        else
            q.push(son[0][i]),fail[son[0][i]]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++)
            if(son[x][i]==-1)
                son[x][i]=son[fail[x]][i];
            else
                q.push(son[x][i]),fail[son[x][i]]=son[fail[x]][i];
    }
    for(int i=1;i<=tot;i++)
        sz[i]=sz[fail[i]]+sz[x];
    for(int i=1;i<=tot;i++)
        f[0][i]=-1e18;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=tot;j++)
            f[i][j]=-1e18;
        for(int j=0;j<=tot;j++)
            for(int k=0;k<26;k++)
                f[i][son[j][k]]=max(f[i][son[j][k]],f[i-1][j]+sz[son[j][k]]);
    }       
    cout<<*max_element(f[m],f[m]+tot+1)<<"\n";
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 10ms
memory: 8548kb

input:

fsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfsfsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfsfsfffsfffssfsfffsfsf...

output:

852

result:

ok single line: '852'

Test #2:

score: 0
Accepted
time: 47ms
memory: 24476kb

input:

ddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttdddddttddttddttddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttddddddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttdddddttddttddttddttddttddttddddtdddttddttddttdddddttddttddt...

output:

5894

result:

ok single line: '5894'

Test #3:

score: 0
Accepted
time: 227ms
memory: 36952kb

input:

wswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswwswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswssswwswwswswwwswswswwwsswswswwwswswswwwswswsswswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswwswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswssswwswwswswwwswsws...

output:

10500

result:

ok single line: '10500'

Test #4:

score: 0
Accepted
time: 25ms
memory: 20292kb

input:

sjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsjssjsspffsjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsjssjssjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsj...

output:

4267

result:

ok single line: '4267'

Test #5:

score: 0
Accepted
time: 221ms
memory: 37652kb

input:

mmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmpmmpmmmppmmpmmmpmmpmpfmzmmpmmmmmpmmmmmpmmmmpmmmpmmpmpfmzmmpmmmmmpfqmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmpmmpmmmppmmpmmmpmmpmpfmzmmpmmmmmpmmmmmpmmmmpmmmpmmpmpfmzmmpmmmmmpfqmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpm...

output:

9536

result:

ok single line: '9536'

Test #6:

score: 0
Accepted
time: 24ms
memory: 20472kb

input:

pepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepyzpepypopepepypgakpepypopepepypopepypopepepyzpepypopepepypepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepypopepepypopepypopepvplpepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepyzpepypopepep...

output:

4033

result:

ok single line: '4033'

Test #7:

score: 0
Accepted
time: 221ms
memory: 37356kb

input:

fifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfiffifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfyqnfifuurfifuugfifuurfifufifuurfifuugfifuurxvfifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfiffifuurfifuu...

output:

9452

result:

ok single line: '9452'

Test #8:

score: 0
Accepted
time: 22ms
memory: 22068kb

input:

gwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgxlggwcgwgxrgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgwvgwgxlggwgxihdggw...

output:

3584

result:

ok single line: '3584'

Test #9:

score: 0
Accepted
time: 0ms
memory: 5832kb

input:

aabaacaabaa
101

output:

249

result:

ok single line: '249'

Test #10:

score: 0
Accepted
time: 0ms
memory: 5672kb

input:

aabaacaabaa
102

output:

251

result:

ok single line: '251'

Test #11:

score: 0
Accepted
time: 0ms
memory: 6152kb

input:

aabaacaabaa
103

output:

253

result:

ok single line: '253'

Test #12:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

aabaacaabaa
104

output:

255

result:

ok single line: '255'

Test #13:

score: 0
Accepted
time: 1ms
memory: 5988kb

input:

aabaacaabaa
105

output:

257

result:

ok single line: '257'

Test #14:

score: 0
Accepted
time: 0ms
memory: 36732kb

input:

cciccpccicc
2000

output:

4995

result:

ok single line: '4995'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

lkultxuuxtkltukllulxkltuutkuuttkuxutuuxuutuxtkxktklltllulkltxtttkkkxxtuxltkxtxtttlltttlkkkutkkuxulklxuuxullkkxtktlxtutuxlktkkllxutlllxkltkutxltxtlluxxlxxxklxlluuxllllxxlllluktkxtkutluktxkkukluktkkuktlkkultukulxlxkltlllkkluluutkxlxkuktktxxtkkkkkuxtxttkxtuxkkttklltulktltxkutluuulluxtuxlllltlutxulxxltk...

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

zrszgeggmmagjcibhsuuugohqppnncuuksrynidfbmhaqpnzswblenhttvtgadwjybijjwhixqppgzqajdqbmjrgaziljastkonutvyqrxtvshhoidkixodyrekyshlafxnikbgaqegxbgwmpgbxnpkdxhnhcocmbpimftogrlydyqitekbfvtimiztujfejkomujzztadjhrvdqlakxnbctuaubumwlwyibmyjabrrdznkvndghplgqjmcvqhmgbsrnpmjjbkkqmnvzczlpsrgdmsmmcgksbkhzatnpiwch...

output:

2

result:

ok single line: '2'

Test #17:

score: 0
Accepted
time: 4ms
memory: 36564kb

input:

xxiiixxhhhxxiiixx
1996

output:

4187

result:

ok single line: '4187'

Test #18:

score: 0
Accepted
time: 0ms
memory: 36656kb

input:

xxiiixxhhhxxiiixx
1997

output:

4190

result:

ok single line: '4190'

Test #19:

score: 0
Accepted
time: 3ms
memory: 36760kb

input:

xxiiixxhhhxxiiixx
1998

output:

4192

result:

ok single line: '4192'

Test #20:

score: 0
Accepted
time: 0ms
memory: 36556kb

input:

xxiiixxhhhxxiiixx
1999

output:

4194

result:

ok single line: '4194'

Test #21:

score: 0
Accepted
time: 0ms
memory: 36856kb

input:

xxiiixxhhhxxiiixx
2000

output:

4196

result:

ok single line: '4196'

Test #22:

score: 0
Accepted
time: 4ms
memory: 36540kb

input:

xxiiixxhhhxxiiixxicpcicpc
2000

output:

4196

result:

ok single line: '4196'

Test #23:

score: 0
Accepted
time: 1ms
memory: 5740kb

input:

c
123

output:

123

result:

ok single line: '123'

Test #24:

score: 0
Accepted
time: 0ms
memory: 36704kb

input:

p
2000

output:

2000

result:

ok single line: '2000'

Test #25:

score: 0
Accepted
time: 7ms
memory: 11872kb

input:

nananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananana
500

output:

40100

result:

ok single line: '40100'

Test #26:

score: 0
Accepted
time: 12ms
memory: 5744kb

input:

czgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczg...

output:

1717

result:

ok single line: '1717'

Test #27:

score: 0
Accepted
time: 229ms
memory: 37496kb

input:

fjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxx...

output:

201000

result:

ok single line: '201000'

Test #28:

score: 0
Accepted
time: 225ms
memory: 36696kb

input:

uuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxpp...

output:

134469

result:

ok single line: '134469'

Test #29:

score: 0
Accepted
time: 37ms
memory: 20396kb

input:

ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

440469

result:

ok single line: '440469'

Test #30:

score: 0
Accepted
time: 230ms
memory: 38524kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

2001000

result:

ok single line: '2001000'

Test #31:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

a
1

output:

1

result:

ok single line: '1'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

z
1

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

cc
1

output:

1

result:

ok single line: '1'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

gg
1

output:

1

result:

ok single line: '1'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

yx
2

output:

2

result:

ok single line: '2'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

tr
2

output:

2

result:

ok single line: '2'

Test #37:

score: 0
Accepted
time: 1ms
memory: 5604kb

input:

xxyxxyx
20

output:

49

result:

ok single line: '49'
English 繁體中文 简体中文

服务器时间: 2024-11-29 20:35:31 | 开源项目