각 문자열을 낮은 차수의 계수부터 적은 위의 다항식으로 생각하자. 문자열의 첫 문자가 이므로 모든 다항식의 상수항은 이다. 시프트 는 다항식에 를 곱하는 것과 같다.
현재 몇 개의 정규화된 다항식이 각각 어떤 위치에서 시작하도록 배치되어 전체 XOR가 이 된다고 가정하자. 가장 작은 시작 위치를 갖는 항은 반드시 두 개 이상이다. 하나뿐이라면 그 위치의 비트를 지울 다른 항이 없기 때문이다.
따라서 시작 위치가 같은 두 항을 하나 골랐다고 가정하고 백트래킹할 수 있다. 두 정규화된 다항식 의 시작 위치를 맞춘 뒤 XOR한다.
가능한 모든 두 항을 골라 재귀한다. 실제 해가 있다면 그 해에서 시작 위치가 최소인 두 항 중 하나를 고르는 분기가 반드시 존재한다. 위 변환 뒤에도 남은 항들의 XOR는 이므로, 이 과정을 반복하면 완전한 해를 찾을 수 있다. 반대로 재귀가 모든 항을 상쇄했다면, 각 병합에서 기록한 상대 위치를 이용해 원래 문자열들의 시프트를 복원할 수 있다.
복원을 위해 각 현재 항에 그 항을 이루는 원래 문자열 번호와 상대 시프트를 저장한다. 두 항을 합친 결과에서 앞의 비트를 제거했다면, 합쳐진 모든 원래 문자열의 상대 시프트에서 를 뺀다. 두 항이 완전히 상쇄되면 그 항에 포함된 상대 시프트의 최솟값을 빼서 최솟값이 이 되도록 만든다. 서로 완전히 상쇄된 묶음은 독립적으로 이동해도 XOR가 계속 이므로, 각 묶음을 따로 정규화해도 된다.
현재 다항식의 길이는 항상 이하이다. 하나의 원래 문자열은 완전히 상쇄되기 전까지 최대 번 정규화될 수 있고, 한 번에 제거되는 비트 수는 최대 이다. 따라서 복원된 시프트는 항상 이상 이하로 만들 수 있다.
각 다항식을 64비트 정수 배열로 저장하면 두 항의 XOR와 정규화를 에 처리할 수 있다. 재귀 트리의 크기는 에만 의존하며 이므로 충분히 작다. 같은 재귀 단계에서 다항식 값이 같은 두 쌍은 하나만 시도하여 중복 분기를 줄일 수 있다.
Solution written by GPT5.6
