1006 （dfs）

#include
using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const int N = 3e5+7;
typedef long long ll;
const ll mod = 998244353 ;
using namespace std;
vector G[N];
int d[N],vis[N];
ll qpow(ll a,ll b){
ll ans=1; ll base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
ll res=1;
ll num=0;
void dfs(int u,int fa,int cnt){
//cout<>n>>m){
for(int i=1;i<=n;i++) G[i].clear(); memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); res=1; num=0; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
vis[1]=1;
dfs(1,0,1);
// for(int i=1;i<=n;i++)
// cout<<d[i]<<endl;
// cout<<res<<endl;
//cout<<num<<endl;
cout<<res*qpow(2,m-num)%mod<<endl;
}
return 0;
}

1010（kmp）

#include
using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const int N = 1e7+7 ;
typedef long long ll;
const ll mod = 998244353 ;
using namespace std;
int nextt[N];
void get_next(string s){
nextt[1]=0;
int len=s.length();
for(int i=2,j=0;i<=len;i++){ while(j>0&&s[j]!=s[i-1]) j=nextt[j];
if(s[j]==s[i-1]) j++;
nextt[i]=j;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll a,b;
while(cin>>a>>b){
string s; cin>>s;
int len=s.length();
int po=0;
for(int i=0;i<len;i++){
if(s[i]=='.'){
po=i;
break;
}
}
s=s.substr(po+1,len-po-1);
reverse(s.begin(),s.end());
get_next(s);
len=s.length();
ll ans=-inf;
for(int i=1;i<=len;i++){
ans=max(ans,a*i-b*(i-nextt[i]));
}
cout<<ans<<endl;
}
return 0;
}