Question: Audify-Tech, Recently Asked in IIT-D for On-Campus Assessments, November 2022
1
Entering edit mode

Question

Seema has got two strings X and Y. Since she likes palindromes, she would like to pick x as some non-empty palindromic substring of X and y as some non-empty palindromic substring of Y. Concatenating them, she would have string XY. Seema feels getting strings this way is interesting, so she wants to evaluate how many unique numbers of strings she can get.

Input

1st line has a single string X (1 <= |X| <= 2 * 10^5)

2nd line has a single string Y (1 <= |Y| <= 2*10^5).

Strings X and Y contain lowercase English letters only (no capital letters).

Output

The first and only line should contain a single integer - the number of possible strings.

Example

Input

xx
xyx

Output

6

Input

xxyx
xyxx

Output

15 

Note: Do not repeat strings, as x+xx = xxx and also xx+x= xxx, but xxx will be counted only once.

ADD COMMENTlink 24 days ago Rohit • 190 • updated 19 days ago QWERTY474 • 40
1
Entering edit mode
ADD COMMENTlink 23 days ago Sahil • 40
1
Entering edit mode
int main(){
    scanf("%s%s",s0+1,s1+1); n0=strlen(s0+1); n1=strlen(s1+1);
    pw1[0]=pw2[0]=ipw1[0]=ipw2[0]=1;
    for (LL i=1,i1=inv1(B1),i2=inv2(B2);i&lt;=n0+n1;++i){
        pw1[i]=pw1[i-1]*B1%mod1;
        ipw1[i]=ipw1[i-1]*i1%mod1;
        pw2[i]=pw2[i-1]*B2%mod2;
        ipw2[i]=ipw2[i-1]*i2%mod2;
    }
    P0.build(s0); P1.build(s1);
    ans=(P0.cnt-1)*(P1.cnt-1);
    for (LL i=0;i&lt;=P0.cnt;++i)
        if (P0.len[P0.fa[i]]&gt;0){
            Hash t=P0.g[i]&lt;&lt;P0.g[P0.fa[i]];
            ++c[0][0][t];
            if (P0.len[i]&lt;=P0.len[P0.fa[i]]*2) ++c[0][1][t];
        }
    for (LL i=0;i&lt;=P1.cnt;++i)
        if (P1.len[P1.fa[i]]&gt;0){
            Hash t=P1.g[i]&gt;&gt;P1.g[P1.fa[i]];
            ++c[1][0][t];
            if (P1.len[i]&lt;=P1.len[P1.fa[i]]*2) ++c[1][1][t];
        }
    for (auto it:c[0][0])
        ans+=(it.second)*c[1][0][it.first];
    for (auto it:c[0][0])
        ans-=(it.second)*c[1][1][it.first];
    for (auto it:c[1][0])
        ans-=(it.second)*c[0][1][it.first];
    for (LL i=1;i&lt;=n0;++i){
        LL x=P0.f[i];
        LL len=P0.len[x];
        vis0[P0.qry(i-len+1,i)]=1;
    }
    for (LL i=1;i&lt;=n1;++i){
        LL x=P1.f[i];
        LL len=P1.len[x];
        vis1[P1.qry(i-len+1,i)]=1;
    }
    memset(vis,0,sizeof vis);
    for (LL i=1;i&lt;=n0;++i){
        LL x=P0.f[i];
        if (vis[x]||P0.len[P0.fa[x]]&lt;=0) continue;
        vis[x]=1;
        LL len=P0.len[x]-P0.len[P0.fa[x]];
        LL l=i-len+1,r=i;
        LL t=P0.double_pld(l,r);
        if (t){
            Hash tmp=P0.qry(l,r)+P0.qry(l,t);
            ans-=vis1[tmp];
        }
    }
    memset(vis,0,sizeof vis);
    for (LL i=1;i&lt;=n1;++i){
        LL x=P1.F[i];
        if (vis[x]||P1.len[P1.fa[x]]&lt;=0) continue;
        vis[x]=1;
        LL len=P1.len[x]-P1.len[P1.fa[x]];
        LL l=i,r=i+len-1;
        LL t=P1.double_pld(l,r);
        if (t){
            Hash tmp=P1.qry(t+1,r)+P1.qry(l,r);
            ans-=vis0[tmp];
        }
    }
    printf("%lld\n",ans);

    return 0;
}
ADD COMMENTlink 19 days ago QWERTY474 • 40

Login before adding your answer.

Similar Posts
Loading Similar Posts