题解：CF919D Substring

这翻译的啥啊，还有一句重要的话没翻，就是如果这个权值可以无限大，就输出 $-1$。

如何让权值无限大，显然是有环。

用拓扑排序判环。

然后就剩下一个 DAG，可以使用 dp。

定义 $dp_{i,j}$ 满足以 $i$ 结尾，出现最多的字母为 $j$ 的路径的最大权值。

若有 $u$ 到 $v$ 的边，那么方程如下：

$$dp_{v,j}=\max(dp_{v,j},dp_{u,j}+[s_v=j])$$

其中 $[s_v=j]$ 表示若 $s_v=j$ 返回 $1$，不然返回 $0$。

最后答案为 $\max_{i=1}^{n}\max_{j=1}^{26}dp_{i,j}$。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[314514],in[314514],dp[314514][26];
vector<int> g[314514];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)a[i+1]=s[i]-'a';
    for(int i=1,u,v;i<=m;i++)cin>>u>>v,g[u].push_back(v),in[v]++;
    queue<int> q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i),dp[i][a[i]]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            for(int i=0;i<26;i++)
                if(a[v]==i)dp[v][i]=max(dp[v][i],dp[u][i]+1);
                else dp[v][i]=max(dp[v][i],dp[u][i]);
            if(!--in[v])q.push(v);
        }
    }
    for(int i=1;i<=n;i++)if(in[i])return cout<<"-1",0;
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<26;j++)
            ans=max(ans,dp[i][j]);
    cout<<ans<<"\n";
    return 0;
}