NC221200. 小圆前辈的博弈
描述
对于取出的任意的两个子串，只要在原串中位置不同我们就认为是不同的取法。
例如：abab中1~2的ab与3~4的ab虽然子串一样，但我们认为是不同的取法。
输入描述
第一行两个整数n，m分别表示S的长度与T的长度。
第二行一个字符串S。
第三行一个字符串T。
输出描述
一个整数表示答案。
示例1
输入:
3 4 aba acac
输出:
4
说明:
小圆前辈可以取出的子串有：a，b，a，ab，ba，aba
小焰同学可以取出的子串有：a，c，a，c，ac，ca，ac，aca，cac，acac
其中当小圆前辈取出b，ab，ba，aba时，小焰同学无法取出与其相同的子串，故小圆前辈必胜。
Java 解法, 执行用时: 1103ms, 内存消耗: 185964K, 提交时间: 2021-05-26 15:57:42
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt(),ans=0;
String a=sc.next(),b=sc.next();
int aa=a.length(),bb=b.length();
for (int i=0;i<aa;i++)
for (int j=i+1;j<=aa;j++)
if(b.indexOf(a.substring(i,j))==-1)ans++;
System.out.println(ans);
}
}
pypy3 解法, 执行用时: 135ms, 内存消耗: 25828K, 提交时间: 2022-03-24 16:07:54
n = int(input())
m = int(input())
# n, m = map(int, input().split())
s = input()
t = input()
ans = 0
for i in range(n):
x = ''
for j in range(i, n):
x += s[j]
if x not in t:
ans += n - j
break
print(ans)
Python3 解法, 执行用时: 54ms, 内存消耗: 4580K, 提交时间: 2022-03-24 17:34:57
n = int(input())
m = int(input())
s = input()
t = input()
cnt=0
for i in range(n):
x = ''
for j in range(i,n):
x += s[j]
if x not in t:
cnt += n - j
break
print(cnt)