Hello! Recently received a task: Write the implementation of the function: Int pos (String search, String where); Where: search - the desired string, where - where we search. The function returns the position of the search string in the string where or -1 if the occurrence was not found. The string is considered an array Char (indexing from 0). Char can be compared with each other. The string has only the length () method, there are no other methods.

I ask for help from more experienced. I decided first with indexOf (), but of course the answer was not counted. I also thought that it was necessary to compare the length of the search string with the lengths of the elements of the where array, but how to put it into the syntax java does not occur.

It is not necessary to write all the code, you can make an analogy, send by reference to similar tasks.

Thank!

  • And why just do not compare polemento? - s8am
  • Most likely it is supposed to use charAt - Russtam
  • no, without charAt'a - e18718
  • you will not find an entry with one length (), and why would there be phrases in the assignment "Consider a string to be an array Char (indexing from 0)"? - Russtam
  • and also, I quote "The string has only the length () method, there are no other methods." I cannot change the conditions of the task, as I would not like. This is one of the first methods that Google gave me, incl. and indexOf (), which was rejected. - e18718

3 answers 3

I will write a variant with a comparison of characters, because The task is most likely a typo and cannot be done with only one length ().

public static int pos(String search, String where) { //искомая строка должна быть не больше той, в которой ищем if (search.length() > where.length()) { return -1; } //ищем только до определенной позиции, т.к. дальше искомая строка уже не "влезет" for (int i = 0; i < where.length() - search.length() + 1; i++) { // если совпадает первый символ ... if (where.charAt(i) == search.charAt(0)) { boolean found = true; // ... то сверим все остальные for (int j = i + 1; j < i + search.length(); j++) { // если хоть один не совпадает ... if (where.charAt(j) != search.charAt(j - i)) { // ... значит не нашли found = false; break; } } // если все символы совпали if (found) { //значит нашли и возвращаем позицию return i; } } } //ничего не нашли return -1; }
  • Thank you very much! Is it not impudent if I ask you to add comments? - e18718
  • You were right, the task is not correct! - e18718

Knuth-Morris-Pratt algorithm, an algorithm taken from here

 public static int[] indexesOf(char[] pattern, char[] text) { int[] pfl = pfl(pattern); int[] indexes = new int[text.length]; int size = 0; int k = 0; for(int i = 0; i < text.length; ++i) { while(pattern[k] != text[i] && k > 0) { k = pfl[k - 1]; } if(pattern[k] == text[i]) { k = k + 1; if(k == pattern.length) { indexes[size] = i + 1 - k; size += 1; k = pfl[k - 1]; } } else { k = 0; } } return Arrays.copyOfRange(indexes, 0, size); } public static int[] pfl(char[] text) { int[] pfl = new int[text.length]; pfl[0] = 0; for(int i = 1; i < text.length; ++i) { int k = pfl[i - 1]; while(text[k] != text[i] && k > 0) { k = pfl[k - 1]; } if(text[k] == text[i]) { pfl[i] = k + 1; } else { pfl[i] = 0; } } return pfl; }

how to use

  String s2 = "ее"; String s1 = "ццццццццццццццееццццуувыфывфыв"; int[] answer = indexesOf(s2.toCharArray() , s1.toCharArray()); for(int q : answer) { System.out.println(q); // 14 }

The array contains all the positions of similar substrings, but it is one and equal to 14

  • Thank you Perhaps this method is a solution, but for my understanding it is currently difficult, as if solving a quadratic equation with a negative root using complex numbers for an 8th grade student. - e18718

you do a search in a loop from zero to the length of where - the length of the search you do the substring of where the length of the search and compare with the search and so iterate step by step with the shift by one character the substring function if you can't use the external one easily enough to write it yourself :)

 for (int i=0; i < where.length() - search.length(); i++){ if (substring(search, i, where.length()) == search) { return i; } }
  • did not quite understand what you wrote. for (int i = 0; i <where.length (); i ++) {search.length () = where.substring (search.length (i)); }? - e18718
  • for (int i = 0; i <where.length () - search.length (); i ++) {if (substring (search, i, where.length ()) == search) {return i; }} - plesser
  • If substring can be used then appropriately where.substr (i, search.length ()); - plesser
  • the string, namely the logical if expression (substring (search, i, where.length ()) == search) is incomprehensible to me, since even before this section of java, I still apparently did not reach. Please write what the topic. - e18718