http://exercise. Acmcoder. com/online/online_judge_ques? ques_id = 3364 & amp; konwledgeid = 40.

Degree bear finding substring ( baidu 2017 real question )


The degree bear receives a string s with only lowercase letters, which is interested in s 's substring, and s 's substring is a continuous segment of s. He found that some substrings were composed of only one letter, and he wanted to know how many strings there were in s.
For example, in string"aaabbaa", degree bear wants to find a substring with"a","aa","aaa","b","bb"five,"bb"five.

( in this case only the number of substrings is considered, the same substring appears only once in multiple locations )

Enter only one line, one string, length not exceeding 100000, and only lowercase
Sample input
Output one line and the number of required substring
Sample output
Time limit
C/c + + language: 1000 ms other languages: 3000 ms
Memory limit
C/c + + language: 65536 kb other languages: 589824 kb
Select language:
Compiler environment description

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;




public class Main {

 public static void main(String[] args) {

 Scanner in = new Scanner(;

 String string = in.nextLine().trim();



 private static int numOfSubString(String string) {

 int index = 0;

 Set<String> set = new HashSet<>();

 for(int i = 0;i<string.length();i++) {

 index = string.charAt(index)==string.charAt(i)?index:i;

 set.add(string.substring(index, i+1));


 return set.size();



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs