10 weeks ago

Rohit • 610

Hyderabad

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.

2.0 years ago

Sahil • 40

https://codeforces.com/problemset/problem/1081/H

2.1 years ago

QWERTY474 • 40

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<=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<=P0.cnt;++i)
        if (P0.len[P0.fa[i]]>0){
            Hash t=P0.g[i]<<P0.g[P0.fa[i]];
            ++c[0][0][t];
            if (P0.len[i]<=P0.len[P0.fa[i]]*2) ++c[0][1][t];
        }
    for (LL i=0;i<=P1.cnt;++i)
        if (P1.len[P1.fa[i]]>0){
            Hash t=P1.g[i]>>P1.g[P1.fa[i]];
            ++c[1][0][t];
            if (P1.len[i]<=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<=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<=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<=n0;++i){
        LL x=P0.f[i];
        if (vis[x]||P0.len[P0.fa[x]]<=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<=n1;++i){
        LL x=P1.F[i];
        if (vis[x]||P1.len[P1.fa[x]]<=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;
}