Как найти индекс лишнего символа, при удалении которого слово становится палиндромом?

Question

[Илья Беликов]

В чём цель программы?
Программа должна вывести единственное число - номер буквы в строке, при удалении которой слово становится палиндромом. Если при удалении любой буквы слово не станет палиндромом, программа должна вывести число 0.

Сама задача звучит так:
Палиндромом называется слово, которое одинаково читается как слева направо, так и справа налево, например, в английском языке такими словами являются "radar" и "racecar".
Света изучает английский язык и решила принять участие в дистанционном конкурсе знатоков английского языка. Но, когда она писала ответ на задание "найдите самое длинное слово, которое является палиндромом", ошиблась и нажала на клавиатуре одну лишнюю клавишу. Определите, какую букву нужно удалить в набранном Светой слове, чтобы это слово стало палиндромом.
Программа получает на вход строку из строчных английских букв, содержащую не менее 2 и не более 100 000 символов.


Моя идея заключается в разделении слова пополам (отдельно для чётного и нечётного количества символов) и проверке попарно элементов (первого и последнего, второго и предпоследнего и т.д) до нахождения несоответствия. После этого индексы уникальной пары сохраняются. Проверяем первый символ пары с символом, идущим сразу за его парой (и то же самое для второго символа, если нужно). Если эти символы совпадают, то выводим индекс буквы, входящей в уникальную пару.

Идея корявая, с реализацией ещё хуже.
Буду благодарен любому дельному совету

Comments

[Andrey Dugin]

Задание создано для того, чтобы вы сделали его самостоятельно и научились. Идите изучайте документацию.

[Илья Беликов]

Andrey Dugin, форум создан для помощи как новичкам, так и совершенствующимся прогерам. Задание олимпиадное, а не домашнее, так что ничего плохого я не вижу в поиске ответа на него здесь.
Будет дельный совет - пишите

[AWEme]

Илья Беликов, на собеседовании тостер вам не поможет.

[Andrey Dugin]

Илья Беликов, в чём конкретно вы совершенствуетесь, если за вас элементарную (тут даже думать не надо!) задачу решит другой человек? Тем более олимпиадную - вам не стыдно? Решайте сами. Если совсем самоуважения нет, идите на фриланс, там за деньги решат. Здесь сайт ответов на вопросы, а не бесплатного выполнения ваших заданий.

[Илья Беликов]

Andrey Dugin, начнём с того, что я не называл себя совершенствующимся программистом. Я в этом деле ещё зелёный, потому и прошу помощи

[Илья Беликов]

AWEme, я пока не собираюсь идти на собеседование. Оно у меня лет через 6 будет

[Andrey Dugin]

Илья Беликов, совершенствуйтесь в изучении документации - у Python она отличная. К тому же где ваш код? Что именно не получается?

Answer 1

[Илья Беликов]

Решение готово (по результатам сайта, который проверял его, оно прошло на 100 баллов из 100 возможных):

def f(c, i, j):
    while i < j:
        if c[i] != c[j]:
            return False
        i += 1
        j -= 1
    return True

c = str(input())
i = 0
j = len(c) - 1

if f(c, i, j):
    print(len(c) // 2 + 1)
    exit()
    
while i < j:
    if c[i] != c[j]:
        if f (c, i, j - 1):
            print(j + 1)
            exit()
        if f (c, i + 1, j):
            print (i + 1)
            exit()
        print('0')
        exit()
    i = i + 1
    j = j - 1

Comments

[Kirixo]

а не подскажете на каком сайте проверяли? потому что эта задача у нас на недельной олимпиаде, а правильно ли решена задача говорится толлько после окончания олимпиады, а хотелось бы проверить решение. лично я парой простых действий в цикле в с++ решил вроде правильно, но есть сомнения по таймлимиту

[Илья Беликов]

Kirixo, проверял на сайте олимпиады школьного этапа по информатике для 9 - 11 классов. Вот ссылка (также нужна регистрация на сайте) - ec2-52-212-178-177.eu-west-1.compute.amazonaws.com...

[Kirixo]

Илья Беликов, Спасибо, там же можно зарегистрироваться и из другой страны?

[Kirixo]

Илья Беликов, там задачи что нельзя ни отправлять ни посмотреть их условие?

[Илья Беликов]

Kirixo, Не обладаю такой информацией

[Илья Беликов]

Kirixo, Возможно это связано со сроками проведения прошедшей олимпиады (Олимпиада проводилась в конце октября). Ничем больше помочь не могу, уж извините.

[Kirixo]

Илья Беликов, всё равно, спасибо. решение помогло.

[Илья Беликов]

Kirixo, рад был стараться

Answer 2

[Yura Khlyan]

Как по мне, то лучше пробегать по всему слову, и по-очереди удалять буквьі и проверять на палиндромность. Если слово палиндром - возвращать индекс той буквьі, если по оканчании прохода не бьіло ниединого палиндрома - вернуть 0

Comments

[Илья Беликов]

Отличная мысль! Спасибо)

[Antonio Solo]

o(n**2)

плохо

Answer 3

[xmoonlight]

Алгоритм (на вскидку, не проверял точность):
length - длина слова
idx - индекс символа слова от любого края по направлению к центру (1,2,3,...)
direction - направление отступа от центра слова (слева: -1; справа: +1)
half - половина длины слова с округлением в большую сторону (при нечётном количестве символов)

half=length+1>>1
direction=-1

1. проверяем слева
2. меняем знак направления отступа: direction*=-1
3. проверяем справа
4. инкрементируем отступ от краёв слова: idx++
5. idx<=half => GOTO 1
6. Позиция: half+direction*(half-idx)

Вариант 2 ("магический"):
1. Взять первую половину слова (через half-форомулу, что выше).
2. Развернуть всё слово и взять также его первую половину. Получим 2 части, которые должны быть равны, если это палиндром.
3. И.... вот, тут, магия: сделать XOR этим двум частям!
4. Первый единичный бит и будет искомая разница.

Comments

[Antonio Solo]

идея интересная

half=round((length+1)/2)

но вот за такое "нахождение середины" я бы тебя на работу не взял ;)

p.s. только ни слова об оптимизирующих компиляторах

[xmoonlight]

Antonio Solo, как правильно?)
half=round(length/2)
так наверно, да?)

[Antonio Solo]

xmoonlight,

сдвиг, а не деление, вот так:

half= length>>1

[xmoonlight]

Antonio Solo, да у меня там всё равно ошибка была (я ж не тестил)
Вот, смари: https://ideone.com/n0Tkrw
Вот так верно: half=length+1>>1
PS:

я бы тебя на работу не взял ;)

так что: 1:1 ;)

[iddqda]

ИМХО правильней вот так
half=length//2 т.е. деление без остатка

просто потому, что если количество букв в слове нечетное,
то проверять центральную букву не имеет смысла. Она всегда является палиндромом самой себе

а уж предпочтение сдвига делению это упоротость.
Я б к такому на работу и не пошел :)

Answer 4

[coderisimo]

имхо, уот так уот :

def testAcronim(word):
  indx = 0 
  for i in word:
    test_string = word[:indx]+ word[indx+1:]
    if test_string==''.join(reversed(test_string)):
      print(indx)
      return
    indx +=1
  print(0)

Comments

[Andrey Dugin]

Я бы на вашем месте не стал помогать этому лентяю. Впрочем, я даже на своём месте не стал.

[coderisimo]

Andrey Dugin, я сейчас сам немного погружаюсь в пайтон , пока смотрел эту задачку - узнал для себя новые штуки. Надеюсь , решение нормальное и у задающего тоже появятся СВОИ идеи.

[longclaps]

coderisimo, решение ненормальное - оно имеет сложность О(N^2), и на строке длины 100000 не пройдёт по времени.
Нормально вот так:

def f(s):
    i, j, k = 0, len(s) - 1, 0
    while i < j:
        if s[i] != s[j]:
            if k:
                k = i
                break
            k = j
        else:
            i += 1
        j -= 1
    print(k, (s[:k], s[k], s[k + 1:]))

f("qwer.tyytrewq")

Answer 5

[Дмитрий Качуринец]

https://jsfiddle.net/or3a71w8/

let word = 'olololo';

function reverseString(str) {
    var splitString = str.split("");
    var reverseArray = splitString.reverse();
    var joinArray = reverseArray.join(""); 
    return joinArray; 
}
 
let reverseWord = reverseString(word);
let result = findIndex(word);

function findIndex(string) {
  if (!isPalindrom(string)) {
    for (let i = 0; i < word.length; i++) {
      let newWord = removeLetter(word, i, 1);
      if (isPalindrom(newWord)) {
       return i;
      }  
      return "C этого слова не сделаешь палиндром";
    }
  } else {
  	return "Это палиндром";
  }
}

function removeLetter(str, startIndex, count) {
    return str.substr(0, startIndex) + str.substr(startIndex + count);
}
function isPalindrom(string) {
	let reversedString = reverseString(string);
	return reversedString === string;
}

console.log(result);

Делал на скорую руку, этот код можно улучшить добавить проверки на колличество символов, делать проверку строка ли это вообще и т.д

p.s. только после написания ответа понял, что это нужно было сделать на питоне) Возможно мой пример на js,
как-то поможет)

Answer 6

[Antonio Solo]

на счет "идеи": честно говоря я не совсем понял что ты хочешь сравнивать после нахождения первого расхождения.
1) идем до расхождения (середина - палиндром)
2) выкидываем слева - продолжаем до расхождения (середина - палиндром)
3) выкидываем справа - продолжаем до расхождения (середина - палиндром)
нет решения

def poly(s):
    L = len(s) - 1
    L2 = (L>>1) + 1
    print(s,L,L2)
    i=0
    while s[i]==s[L-i]:
        print('1:', i, s[i], s[L-i])
        i+=1
        if i==L2: return 0
    print('2:', i, s[i], s[L-i])
    k=i
    while s[k+1]==s[L-k]:
        print('3:', k, s[k+1], s[L-k])
        k+=1
        if k==L2: return i
    print('4:', k, s[k], s[L - k])
    k=i
    while s[k]==s[L-k-1]:
        print('5:', k, s[k], s[L-k-1])
        k+=1
        if k==L2: return L-i
    print('6:', k, s[k], s[L - k])
    return None
while True:
    s = input()
    print(s)
    print(poly(s))

qwertyytrewq
qwertyytrewq
qwertyytrewq 11 6
1: 0 q q
1: 1 w w
1: 2 e e
1: 3 r r
1: 4 t t
1: 5 y y
0
qwertyytrwq
qwertyytrwq
qwertyytrwq 10 6
1: 0 q q
1: 1 w w
2: 2 e r
3: 2 r r
3: 3 t t
3: 4 y y
3: 5 y y
2
qwrtyytrewq
qwrtyytrewq
qwrtyytrewq 10 6
1: 0 q q
1: 1 w w
2: 2 r e
4: 2 r e
5: 2 r r
5: 3 t t
5: 4 y y
5: 5 y y
8
qwertyytrewqww
qwertyytrewqww
qwertyytrewqww 13 7
2: 0 q w
3: 0 w w
4: 1 w w
6: 0 q w
None