題目描述?

給定兩個等長的由小寫字母構成的串?$\mathrm{A,BA,B，其中?|A|=|B|=n|A|=|B|=n。現在你需要求出一個子區間?[l,r][l,r]?使得?LCP(A[l,r],B[l,r])\times LCS(A[l,r],B[l,r])+LCP(A[l,r],B[l,r])+LCS(A[l,r],B[l,r])LCP(A[l,r],B[l,r])\times LCS(A[l,r],B[l,r])+LCP(A[l,r],B[l,r])+LCS(A[l,r],B[l,r])?最大，并輸出這個值。}$ $\mathrm{LCP(S,T)LCP(S,T)表示S和T的最長公共前綴，LCS(S,T)LCS(S,T)表示S和T的最長公共后綴。}$

輸入描述:

第一行一個字符串 $\mathrm{AA。第二行一個字符串?BB\; 。}$

輸出描述:

一行一個整數，表示答案。 示例1

輸入

復制 aaabbbcccddd aaaddddddddd

輸出

復制 15

說明

選擇?$\mathrm{l=1,r=12l=1,r=12\; 是一種可行的最優解。}$

備注:

對于所有數據，保證?$\mathrm{n\le 200000n\le 200000\; ，串?A,BA,B\; 僅由小寫字母構成。}$



1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 #include <cmath> 8 #include <queue> 9 #include <set> 10 #include <map> 11 #include <stack> 12 #define pi acos(-1.0) 13 #define ll long long 14 #define P pair<ll,ll> 15 #define pu push_back 16 using namespace std; 17 const int N =2e5+1000; 18 char s[N],p[N]; 19 ll mx1,mx2; 20 //題意很簡單，注意一定要前后都掃一遍（我只掃了一遍，不停WA） 21 //因為可能是同一個小區間，此時就取那個區間 22 //如 ab cb 1*1+1+1=3 23 int main() 24 { 25 scanf("%s%s",s,p); 26 int l =strlen(s); 27 mx1=0,mx2=0; 28 ll ans=0;//ans :當前狀態下公共綴的長度，只要s,p的某個對應字母一樣就有公共綴了。 29 //起初，一直在考慮必須至少連續兩個一樣才有公共綴（錯誤） 30 for(int i =0;i<l;i++){ 31 if(s[i]==p[i]) { 32 ans++; 33 } 34 else{ 35 ans=0; 36 } 37 mx1=max(mx1,ans); 38 } 39 ans=0; 40 for(int i =l-1;i>=0;i--){ 41 if(s[i]==p[i]) { 42 ans++; 43 } 44 else{ 45 ans=0; 46 } 47 mx2=max(mx2,ans); 48 } 49 printf("%lld\n",mx1*mx2+mx1+mx2); 50 return 0; 51 }

?

轉載于:https://www.cnblogs.com/tingtin/p/10543016.html

總結

以上是生活随笔為你收集整理的牛客练习赛42 A字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。