weixin_47387970
2020-11-07 17:56
采纳率: 57.1%
浏览 22
已采纳

求大佬们帮忙看一道算法题目

我好菜啊,做了半天还是做不出来,题目如下:

提取子序列 subarr

Description

 

「信息学(Informatics)」的另一个译名是「情报学」,这个名字在日本见得比较多。日文的「情報」读音为「Jyouhou」。

现在有一个长为 nn 的字符串 SS ,SS中只包含大小写英文字母或数字。按从前往后的顺序读字符串SS,从SS中取出最靠前的一个子序列构成Jyouhou串,取出一个串后,从最后一个字符的后一个位置继续尝试取出,直到剩余部分已无法取出一个Jyouhou串。请求出对于给定的SS,取出的Jyouhou串的数量是多少。

子序列:从一个序列中取出若干元素(不要求相邻)组成的一个新序列,新序列元素的顺序按照原序列中元素的相对顺序确定。

你可以参考样例解释来帮助理解上面的流程。

Input

 

测试点包含多组测试数据。

第一行包含一个正整数T (1≤T≤20),表示测试数据组数。

每组数据中包含两行。第一行包含一个正整数n (1≤n≤10^4),表示字符串SS的长度。第二行包含一个字符串SS,含义见「题目描述」。

Output

 

对于每一组测试数据,输出一行一个正整数,表示该组数据的答案。

Sample Input 1 

3
20
JJSy2ouhuouJ5yoxuhou
10
aaaaaaaaaa
14
JyouhoJuyouhou

Sample Output 1

2
0
1

第一组数据中,找到的 2 个Jyouhou串为JJSy2ouhuouJ5yoxuhou

第二组数据中,由于不存在 J、y、o、u、h 字符,故无法找到任何一个Jyouhou串。

第三组数据中,找到的Jyouhou串为JyouhoJuyouhou。由于前一个Jyouhou串的最后一个字符 u 在第二个字符 J 前面,字符 u 后面已经无法再找到一个Jyouhou串了,因此只能找出 1 个。

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • qq_25376897 2020-11-12 17:41
    已采纳
    public static void main(String[] args){
        String target = "Jyouhou";//目标串
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();//组数
        if(t<=0){
            System.out.println("组数必须大于0");
            return;
        }
        int tLen = target.length();//目标串长度
        String[] s = new String[t];//需要匹配的字符串数组
        for(int i=0;i<t;i++){
            int n = scanner.nextInt();
            if(n<=0){
                System.out.println("字符串SS的长度必须大于0");
                return;
            }
            scanner.nextLine();//消化掉回车,避免下面的nextLine读到
            String s1 = scanner.nextLine();
            s[i]= s1.substring(0,n);
        }
    
        for(int i=0;i<t;i++){
            int count = 0;//匹配的次数
            int k1 = 0;
            int k2 = 0;
            int sLen = s[i].length();//源字符串的长度
            if(sLen<tLen){//长度不够,肯定不匹配
                System.out.println(0);
            }else{
                while(true){
                    if(s[i].charAt(k1)==target.charAt(k2)){
                        k2++;
                    }
                    k1++;
                    if(k2==tLen){//target被遍历完,res计数,k2重新开始
                        count++;
                        k2=0;
                        if(sLen-k1<tLen){ //如果剩余长度不足,没必要往下判断
                            System.out.println(count);
                            break;
                        }
                    }
                    if(k1==sLen){//源字符串已被扫描完,输出
                        System.out.println(count);
                        break;
                    }
                }
            }
        }
    }
    已采纳该答案
    1 打赏 评论

相关推荐 更多相似问题