复习
2025-12-18 22:49:54
发布于：上海
1阅读
0回复
0点赞
废话可以选择性观看
啊啊啊啊啊不舒服就回家了
开始时间：2025/12/17 13:18
继续做天天酷跑吧
做了几十行，样例没过啊qwq，得再调
啊啊啊啊做不动了 摸了两个小时 摸了10pts
谁来拯救我？
你说是有人突然读懂了我吗？
不，这太荒谬，太像穷荒之旅上突然出现的一朵月季，鲜红灿烂不真实。
我始终无法想象，谁会能透过我贫瘠的外表，总是被厚玻璃覆盖的双眼，看清我那一片荒芜满是杂草的心。
我都无法看清我自己。
因为当我终想起应该望向自己时，我的双眸早已被满眶泪水充溢。
眼前总是一片模糊，清晰是真实也是假象。
——————————————————————————————————
好的，今天复习kmp算法。
开始时间：2025/12/18 21:00
从模板开始吧！
我想想怎么做的……链接描述
先求一个nxt数组，然后去查找吧。
怎么求nxt数组的来着？
我去搓搓看。
啊啊啊写出来了
代码鉴赏：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N];
int main(){
string s1,s2;
cin>>s1>>s2;
int i=1;
int len=0;
while(i<s2.size()){
if(s2[i]==s2[len]){
nxt[i++]=++len;
}else{
if(len==0)i++;
else len=nxt[len-1];
}
}
int j;
i=j=0;
while(i<s1.size()){
if(s1[i]==s2[j]){
i++,j++;
}else{
if(j==0)i++;
else j=nxt[j-1];
}
if(j==s2.size())cout<<i-j+1<<endl;
}
for(int i=0;i<s2.size();i++)cout<<nxt[i]<<" ";
return 0;
}
然后去看一下另一道题，无线传输。
这应该是我最喜欢的一道题目吧。波罗的海。Baltic。
它的题意大概是：
给出一个由字符串s2不断连接形成的字符串s1，现在想问s2的最小长度。
在我的记忆里，这道题目帮我翻新了对nxt数组的印象。
但是我现在不记得它是怎么做的了。
我想起来结论了
n-nxt[n-1]可是为什么？
啊啊啊啊我懂了，不过过程有点复杂，这里就不写了（我录了讲解视频嘻嘻。
然后，然后我去搓代码了。
过啦嘻嘻
看个代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int nxt[N];
int main(){
int n;
cin>>n;
string s1;
cin>>s1;
int i=1;
int len=0;
while(i<s1.size()){
if(s1[i]==s1[len]){
// cout<<nxt[i]<<" "<<len+1<<endl;
nxt[i++]=++len;
}
else{
if(len==0)i++;
else len=nxt[len-1];
}
}
cout<<n-nxt[n-1];
return 0;
}
老师好像发了个什么题单，但不想做，默认没看到。
去做啥呢？
去码头搞点蓝题做做吧（海鸥音
试试看这个吧链接描述
我不会 但我不想承认 我c了
好烦
这题怎么回事
我不做了
结束时间：2025/12/18 22:49
这里空空如也
有帮助，赞一个