网站流量统计分析报告,网站后台传不上图片,深圳横岗做网站的,网站建设要什么软件有哪些2023牛客暑期多校训练营8-I Make It Square
https://ac.nowcoder.com/acm/contest/57362/I 文章目录 2023牛客暑期多校训练营8-I Make It Square题意解题思路代码实现 题意 解题思路
这里有两种情况#xff0c;即 ∣ s ∣ ∣ t ∣ |s||t| ∣s∣∣t∣和 ∣ s ∣…2023牛客暑期多校训练营8-I Make It Square
https://ac.nowcoder.com/acm/contest/57362/I 文章目录 2023牛客暑期多校训练营8-I Make It Square题意解题思路代码实现 题意 解题思路
这里有两种情况即 ∣ s ∣ ∣ t ∣ |s||t| ∣s∣∣t∣和 ∣ s ∣ ∣ t ∣ |s||t| ∣s∣∣t∣首先考虑 ∣ s ∣ ∣ t ∣ |s||t| ∣s∣∣t∣的情况对于不同的 m m m有两种情况用图画来表示下面两种情况 显然对于每一种情况都要判断 t t t是否与 s 1 s_1 s1的后缀相同。否则答案必为 0 0 0。 如图对于第一种情况即 p p p与 q q q有重叠设重叠部分有 k k k个元素其答案显然为 2 6 k 26^k 26k; 对于第二种情况还需要判断 s 2 s_2 s2与 s 1 s_1 s1的重叠部分是否相同。 判断 s 2 s_2 s2与 s 1 s_1 s1的重叠部分相同不需要一一枚举可以发现重叠部分即是 s s s的相同的前缀与后缀可以用 k m p kmp kmp算法中的求 n e x t next next数组的方法来求。 而对于 ∣ s ∣ ∣ t ∣ |s||t| ∣s∣∣t∣可以发现若交换 t t t与 s s s不会影响最终答案如下图 左图中上下 s s s对应的 t t t的区域距 t t t尾部都是 p / q p/q p/q右图中上下 s s s对应的 t t t的区域距 t t t头部都是 t 1 − t 2 / q 1 t_1-t_2/q_1 t1−t2/q1显然 t 2 q 2 t_2q_2 t2q2所以 s s s所对的区域都相同 s s s显然相同所以交换后 1 1 1还是 1 1 1 0 0 0还是 0 0 0 2 6 k 26^k 26k还是 2 6 k 26^k 26k。
代码实现
#includebits/stdc.h
using namespace std;
const int N1e65,mod998244353;
int m,nx[N];
long long ans[N];
char a[N],b[N];
int main(){cinm;scanf(%s %s,a1,b1);int Astrlen(a1),Bstrlen(b1);if((AB)%2){for(int i1;im;i)cout0 ;return 0;}if(AB)swap(a,b),swap(A,B);int k0,f0;nx[1]0;for(int i2;iA;i){while(k0a[k1]!a[i])knx[k];if(a[k1]a[i])k;nx[i]k;}int d(AB)/2,rA-d;for(int i1;iB;i){if(b[i]!a[d-Bi]){for(int i1;im;i)cout0 ;return 0;}}fnx[A];while(f0){if(fr)ans[r-f]1;fnx[f];}ans[r]1;for(int ir1;im;i)ans[i]ans[i-1]*26%mod;for(int i1;im;i)coutans[i] ;
}
