eipie's blog

By eipie, 12 years ago, In English

Can someone help me find the java version specific bug or whatever here? Or the problem with my code Thanks!

Here is my code for the Petr# problem (113B - Petr#)

import java.util.*;
public class B {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		String start = sc.next();
		String finish = sc.next();
		
		ArrayList<Integer> s = new ArrayList<Integer>();
		ArrayList<Integer> e = new ArrayList<Integer>();
		for (int i=0; i<input.length(); i++) {
			if (startsWith(input,start,i)) {
				s.add(i);
			}
			if (startsWith(input,finish,i)) {
				e.add(i);
			}
		}
		
		if (s.isEmpty() || e.isEmpty()) {
			System.out.println(0);
			return;
		}
				
		if (start.equals(finish)) {
			System.out.println(s.size());
			return;
		}
		
		HashSet<Integer> ans = new HashSet<Integer>();
		for (int i=0; i<s.size(); i++) {
			for (int j=0; j<e.size(); j++) {
				int x = e.get(j)-s.get(i);
				if (x<0)
					continue;
				ans.add(x);	
			}
		}
		System.out.println(ans.size());
	}
	
	private static boolean startsWith(String str, String search, int start) {
		if (str.length()-start < search.length())
			return false;		
		for (int i=0; i<search.length(); i++)
			if (str.charAt(start+i) != search.charAt(i))
				return false;
		return true;
	}
}

The input in question is: (the first word is split into two lines please make it ONE word)

adsflkdsjfmbvcxnvaeshjadskfnxvbrusighjdzbnxmgaldfbhzxnvbxcmvgaslugkzxcnbvxcnbvaselugtnbvzncblasjdfgnvbxzfalsdjgfadsgvbxcnvsayurqejhkdjzbvnzcgbgaskehgfmnbvmcvgasdgfnmbcvzmcvgadjtgaweuvxzcbvnxzcbfkahsgfbvznvbxzckugadjfasbvnzxcbvkdsjghdfskjbvxzmnbfalsefgsadhjvbznvbzxkngfsadkhfbxcvznbvkaedgfabvzncxvbzxckmbasdjgfbvnbzmvbzljrgfsahjvbxcnvbasdhfgjdsgvbxcnbasldgfsdujfdsjvbxmvbasdkhgfasdjfbasdnfbnvbxckvbadsuilfhadsjfbzvxcnbcxfgadujgadsjbvnbzvrjlghdsjhvnxncbvlsadjhadjshfasdkljfgfbdghfjbjfiadjvcnvsdjfbdvbjdshfkjehfldsakjhfjsadkhfksadljhfjsadklhfdsjakhfiewuyriubvznbxcvncbvzxuwqejnxcffeivbdqwetgrfvxcjmshbdfkjhwqrerfhsdjkvhbjwegfbxcdfjshnvhjdvhbfjsfdhbvdsajffvdhsabjfhvbeuofyrvboewufsadjhfvasdjhfvbsadlfvhsadljhfvbsadlvfsad

lkvfhsadljfvbhasdlfvbewvbwyufvbsaduyfvbsadjvhzlbvzxjchbvdufhdasjvfbhyeuwvbfuadhvbjsadvbfasbdhvfaoiuryweqiuyruqoweiyrsdfbhvdsjfhabsldfbvejhdsaiufyewiuqryqweiouvyrbwqeiubvriuwqeyvbbajsdhfvasdkfasdljkbfvhhajlsdhfvbcxzgahsjdkchnbxnuigeahfgdshfgdaskhfgsadkhfgadshfgdsahfgdaskhsadkfhgsadkhfgsadfkhdgsfkgdsakhfgdaskhfgasdkfgasdhfgdsafhadsgfksagfhkdsagfksadhfgbzncvbxnzcvbdlsjfhdsajflgwehjgtrdznbvcxmxcvblasdjhfaljsdkfhalsdkjfhasdkljfhalsdkjfhiewuytololonobodywillseethatdsjkfjaljxcmvxcbghfdjghdfjkhgdfjlsghfsdljhsdflghdfsjghfsdjlbcxnvnmcxzmnvxzcvbzxcmvbzxmcvbzxcnvbdsuagtywequityudhgjdkshgjklsdhgjfdkhgjlfsdkghlsdkfghdjfhgfdjghjkasdfhldsakjhfasjdklfhxcvnzbxcvnzbcxmvzcxhdsafjlsadjfhsadljhfieurytoueqytuihdfgkhsdflkjhvtyuweturetyurweotpqoewtguregdjkgbcxzmvbczvmzbxcnvzxsdahfuleyuyqetuiy
ad
iy
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

"Substrings are different if and only if their contents aren't equal, their positions of occurence don't matter." You are comparing length of this substrings. Use hachcodes.

  • »
    »
    12 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Gotcha. So...

    a) my algorithm is wrong: abcPxyz abcQxyz are two different substrings but according to my logic they would be considered the same. HashCodes are indeed the easiest way to solve this problem of mine. Thanks.

    b) The original problem I faced was that I get the answer as 63 when running my code on my local machine (which is what Codeforces expects). But for some reason http://codeforces.com/contest/113/submission/1312277 says that my code actually outputs 62. So that is what I was trying to figure out.

    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it +15 Vote: I do not like it

      i don't know what's wrong with that test, but i think there is another WA test:

      abcde cde cd

      correct answer is 0