6200: 积木小赛

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

Alice 和 Bob 最近热衷于玩一个游戏——积木小赛。
Alice 和 Bob 初始时各有 块积木从左至右排成一排,每块积木都被标上了一个英
文小写字母。
Alice 可以从自己的积木中丢掉任意多块(也可以不丢); Bob 可以从自己的积木中
丢掉最左边的一段连续的积木和最右边的一段连续的积木(也可以有一边不丢或者两边
都不丢)。两人都不能丢掉自己所有的积木。然后 
Alice 和 Bob 会分别将自己剩下的积
木按原来的顺序重新排成一排。
Alice 和 Bob 都忙着去玩游戏了,于是想请你帮他们算一下,有多少种不同的情况
下他们最后剩下的两排积木是相同的。
两排积木相同,当且仅当这两排积木块数相同且每一个位置上的字母都对应相同。
两种情况不同,当且仅当 Alice(或者 Bob)剩下的积木在两种情况中不同。

Input

第一行一个正整数 n,表示积木的块数。
第二行一个长度为 
的小写字母串 s,表示 Alice 初始的那一排积木,其中第 
字母 
s表示第 块积木上的字母。
第三行一个长度为 
的小写字母串 t,表示 Bob 初始的那一排积木,其中第 个字
母 
t表示第 块积木上的字母。

Output

行一个非负整数表示答案

Sample Input Copy

样例1
5
bcabc
bbcca

样例2
20
egebejbhcfabgegjgiig
edfbhhighajibcgfecef

Sample Output Copy

样例1
9

样例2
34

HINT

样例1
用所标的字母代替每块积木,那么 Alice 剩下的那排积木依序为 a, b, bb, bbc
bc, bcc, c, ca 或者 cc 时, Bob 剩下的那排积木可以与 Alice 的相同

对于所有测试点: ≤ ≤ 3000, 与 中只包含英文小写字母。
测试点 
满足: ≤ 3000, 与 中只包含同一种字母。
测试点 
∼ 满足: ≤ 100
测试点 
∼ 满足: ≤ 500
测试点 
∼ 10 满足: ≤ 3000

Source/Category