Подсчитать вхождение строки иглы в строку Haystack, наиболее оптимально?

Question

Проблема проста Найти «ABC» в «ABCDSGDABCSAGAABCCCCAAABAABC» без использования String.split («ABC»)

Вот решение, которое я предлагаю, я ищу любые решения, которые могут быть лучше, чем этот.

public static void main(String[] args) {
 String haystack = "ABCDSGDABCSAGAABCCCCAAABAABC";
 String needle = "ABC";
 char [] needl = needle.toCharArray();
 int needleLen = needle.length();
 int found=0;
 char hay[] = haystack.toCharArray();
 int index =0;
 int chMatched =0;

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

  if (index >= needleLen || chMatched==0)
   index=0;
  System.out.print("\nchar-->"+hay[i] + ", with->"+needl[index]);

  if(hay[i] == needl[index]){
   chMatched++;
   System.out.println(", matched");
  }else {
   chMatched=0;
   index=0;
   if(hay[i] == needl[index]){
    chMatched++;
    System.out.print("\nchar->"+hay[i] + ", with->"+needl[index]);
    System.out.print(", matched");
   }else
   continue;
  }

  if(chMatched == needleLen){
   found++;
   System.out.println("found. Total ->"+found);
  }
  index++;
 } 
 System.out.println("Result Found-->"+found);
 }

Мне понадобилось время, чтобы создать этот. Может кто-нибудь предложить лучшее решение (если есть) Постскриптум Бросьте sysouts, если они выглядят вам грязно.

Answer 1

Как насчет:

boolean found = haystack.indexOf("ABC") >= 0;

** Редактировать - вопрос спрашивает количество случаев, так что вот модифицированная версия выше:

public static void main(String[] args)
{
    String needle = "ABC";
    String haystack = "ABCDSGDABCSAGAABCCCCAAABAABC";

    int numberOfOccurences = 0;
    int index = haystack.indexOf(needle);
    while (index != -1)
    {
        numberOfOccurences++;
        haystack = haystack.substring(index+needle.length());
        index = haystack.indexOf(needle);
    }

    System.out.println("" + numberOfOccurences);
}

Answer 2

Если вы ищете алгоритм , поищите в Google "Boyer-Moore".Вы можете сделать это за сублинейное время.

edit , чтобы прояснить и, надеюсь, осчастливить всех пуристов: время, ограниченное Бойер-Муром, формально говоря, линейно.Однако эффективная производительность зачастую такова, что вы выполняете намного меньше сравнений, чем при более простом подходе, и, в частности, вы часто можете пропустить строку «стог сена», не проверяя каждый символ.

Answer 3

public class NeedleCount
{
  public static void main(String[] args)
  {
    String s="AVBVDABCHJHDFABCJKHKHF",ned="ABC";
    int nedIndex=-1,count=0,totalNed=0;
    for(int i=0;i<s.length();i++)
    {
      if(i>ned.length()-1)
        nedIndex++;
      else
        nedIndex=i;
      if(s.charAt(i)==ned.charAt(nedIndex))
        count++;
      else
      {
        nedIndex=0;
        count=0;
         if(s.charAt(i)==ned.charAt(nedIndex))
          count++;
        else
          nedIndex=-1;
      }
      if(count==ned.length())
      {
        nedIndex=-1;
        count=0;
        totalNed++;
        System.out.println(totalNed+" needle found at index="+(i-(ned.length()-1)));
      }
    }
    System.out.print("Total Ned="+totalNed);
  }
}

Answer 4

Посмотрите на http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Answer 5

Вы говорите, что ваша задача найти ABC в строке. Если все, что вам нужно, это знать, существует ли ABC в строке, достаточно простого теста indexOf().

Если вам нужно узнать количество вхождений, поскольку ваш опубликованный код пытается найти, простой подход - использовать регулярное выражение:

public static int countOccurrences(string haystack, string regexToFind) {
   Pattern p = Pattern.compile(regexToFind);
   Matcher m = p.matcher(haystack); // get a matcher object
   int count = 0;
   while(m.find()) {
       count++;
   }
   return count;
}

Answer 6

    public class FindNeedleInHaystack {

        String hayStack="ASDVKDBGKBCDGFLBJADLBCNFVKVBCDXKBXCVJXBCVKFALDKBJAFFXBCD";
        String needle="BCD";
        boolean flag=false;

        public void findNeedle() {
//Below for loop iterates the string by each character till reaches max length
            for(int i=0;i<hayStack.length();i++) {  
//When i=n (0,1,2... ) then we are at nth character of hayStack. Let's start comparing nth char of hayStach with first char of needle
                if(hayStack.charAt(i)==needle.charAt(0)) {
//if condition return true, we reach forloop which iterates needle by lenghth.
//Now needle(BCD) first char is 'B' and nth char of hayStack is 'B'. Then let's compare remaining characters of needle with haystack using below loop. 
                    for(int j=0;j<needle.length();j++) {
//for example at i=9 is 'B', i+j is i+0,i+1,i+2...
//if condition return true, loop continues or else it will break and goes to i+1
                        if(hayStack.charAt(i+j)==needle.charAt(j)) {
                            flag=true;
                        } else {
                            flag=false;
                            break;
                        }
                    }
                    if(flag) {
                        System.out.print(i+" ");
                    }
                }                               
            }
        }
    }

Answer 7

Если вы не возражаете против внедрения новой структуры данных в качестве замены строк, взгляните на «Пытания»: http://c2.com/cgi/wiki?StringTrie или http://en.wikipedia.org/wiki/Trie

Если вы ищете не регулярное выражение, а точное совпадение, они должны предоставить самое быстрое решение (пропорционально длине строки поиска).

Answer 8

Спросили другие, лучше в каком смысле? Решение на основе регулярных выражений будет наиболее кратким и читаемым (:-)). Бойер-Мур (http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm) будет наиболее эффективным с точки зрения времени (O (N)).

Answer 9

А как насчет рассмотрения регулярных выражений, классов Pattern и Matcher? Проверьте этот учебник