Может ли кто-нибудь предложить лучший подход для сравнения строк между двумя строками с не более чем одним несовпадением.
Пример:
- A: abcdefghabX
- B: abc
- Выход: 1 9
Вышевыходные данные - это позиции совпадений подстрок abc в «A»
Я попробовал базовый подход с двумя циклами for, но, похоже, он занимает N * N времени.Это большой фактор для больших входных данных и занимает огромное количество времени.
Мой алгоритм как таковой, но он не самый лучший для большого количества данных
int compare(string a, int pos, string b)
{
int count = 0;
int length = b.length()-1;
int mid = b.length() /2;
if(pos+length >= a.length())
return 0;
if((length+1)%2 != 0) {
for(int i=0,j=pos;i<=mid;i++,j++) {
if(i == mid) {
if(a[j] != b[i])
count ++;
}
else {
if(a[j] != b[i])
count ++;
if(a[pos+length - i] != b[length -i])
count ++;
}
if(count >= 2) return 0;
}
}
else {
for(int i=0,j=pos;i<mid;i++,j++) {
if(i == mid) {
if(a[j] != b[i])
count ++;
}
else {
if(a[j] != b[i])
count ++;
if(a[pos+length - i] != b[length -i])
count ++;
}
if(count >= 2) return 0;
}
}
return 1;
}