java implementation of the string return function in a string only by the length method
Hello! Recently received a task: Write a function implementation: Int pos(String search, String where); Where: search-the search string, where - where we are looking for. The function returns the position of the search string in the where string, or -1 if no occurrence is found. The string is considered an array of 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 ones. I decided first using indexOf(), but naturally, the answer was not counted. I also thought that you need to compare the length of the search string with the lengths of the elements of the where array, but how to pour it into the java syntax does not come to mind.
It is not necessary to write all the code, you can give an analogy, direct links to similar tasks.
Thanks!
3 answers
I will write a variant with a comparison by character, because the task is most likely a typo and it is impossible to do it 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;
}
Knuth-Morris-Pratt algorithm, taken from here algorithm
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 the same and is equal to 14
You do the search in a loop from zero to the length of where-the length of search you do the substring from where with the length of search and compare it with search and so iterate stepwise with a shift of one character the substring function if you can not use the external one, it is quite easy to write yourself :)
for (int i=0; i < where.length() - search.length(); i++){
if (substring(search, i, where.length()) == search) {
return i;
}
}