求助 这个做法复杂度
查看原帖
求助 这个做法复杂度
341245
Sunflower_ac楼主2023/10/28 16:54

请问如下代码这种跳 lst 的做法为啥是 O(n∣Σ∣)O(n|\Sigma|)?实在想不明白了。

for(int i=1;i<=n;i++)
{
  for(int j=i-1;j>0;j=lst[j]-1)
  {
    if(s[i]==s[j])
    {
      lst[i]=j;break;
    }
  }
  if(lst[i])dp[i]=dp[lst[i]-1]+1,ans+=dp[i];
}
cout<<ans<<'\n';
2023/10/28 16:54
加载中...