Я хочу проверить, является ли шаблон подстрокой s, но я хочу проверить его от последнего до первого индекса. Например
s="Привет, как дела";
шаблон = "Есть"
и возвращает индекс e->12. потому что от последнего к первому в строке шаблона мы сначала видим букву e.
ниже я беру свой код. Как я могу это исправить?
class Main {
static int find(String s1, String s2) {
int M = s1.length();
int N = s2.length();
for (int i = N - 1; i >= 0; i--) {
int j;
for (j = M - 1; j >= 0; j--)
if (s2.charAt(i) != s1.charAt(j))
break;
if (j == 0)
return i;
}
return -1;
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
System.out.println("Please Enter first String: ");
String s = scanner.nextLine();
System.out.println("Please Enter Pattern String: ");
String pat = scanner.nextLine();
int res = find(pat, s);
if (res == -1)
System.out.println(res);
else
System.out.println("Present at index " + res);
}
}
Обратите внимание, что когда вы перебираете шаблон, вы также должны поддерживать некоторую итерацию в подстроке «первой строки», чтобы вы сравнивали каждую букву в шаблоне с соответствующей буквой в подстроке. Что-то подобное:
static int find(String s1, String s2) {
int M = s1.length();
int N = s2.length();
for (int i = N-1; i >=0; i--) {
int j;
int k = i;
for (j = M-1; j >0; j--)
if (s2.charAt(k) != s1.charAt(j))
break;
else
k--;
if (j==0)
return k + (M-1);
}
return -1;
}
и как я могу узнать временную сложность этого кода? @иданз
@megan, если мы предположим, что длина первой строки равна n, а длина шаблона равна k - в худшем случае для каждого символа первой строки мы делаем k итераций, чтобы попытаться сопоставить шаблон. Так что это O(n*k)
public class Main {
static int find(String s1, String s2) {
return s1.lastIndexOf(s2)+s2.length()-1;
}
public static void main(String[] args) {
String str = "Hello How Are you";
String pattern = "Are";
System.out.println(find(str,pattern));
}
}
Переверните обе строки (s и шаблон). Затем найдите шаблон в заданной строке. Индекс результата будет => размер строки - индекс найденного шаблона