For \(0 \le i \lt n\), define
$$a_i=\operatorname{popcount}(i)\bmod 2,\qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor-\left\lfloor\frac{i}{\varphi}\right\rfloor,\qquad c_i=a_i\oplus b_i,$$
where \(\varphi=\frac{1+\sqrt{5}}{2}\). The binary word of interest is
$$C_n=c_0c_1\dots c_{n-1}.$$
For each \(k\ge 1\), let \(L_n(k)\) be the maximum length of a substring of \(C_n\) that occurs at least \(k\) times, allowing overlaps. The task is to evaluate
$$\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
for \(n=5{,}000{,}000\). Since \(C_n\) has millions of positions and \(O(n^2)\) distinct substring intervals, the solution must compress the repeated-substring structure instead of enumerating substrings directly.
Once the word \(C_n\) has been generated, the problem becomes a pure substring-frequency question for one fixed binary string. The decisive tool is a suffix automaton, because it stores all distinct substrings in linear space together with enough structure to recover how many times each substring appears.
The first ingredient, \(a_i\), is the parity of the number of \(1\)-bits in the binary expansion of \(i\), so it is the Thue-Morse bit at index \(i\). The second ingredient, \(b_i\), is a Beatty difference. Since \(\frac{1}{\varphi}=\varphi-1\in(0,1)\), the sequence
$$\left\lfloor\frac{i}{\varphi}\right\rfloor$$
can increase by at most \(1\) when \(i\) is incremented, hence
$$b_i\in\{0,1\}.$$
Therefore \(c_i=a_i\oplus b_i\) is again binary, and the entire input to the substring problem is a binary word \(C_n\). Generating the word costs only \(O(n)\) time, one position at a time.
A suffix automaton for \(C_n\) groups substrings by their set of end positions. Each state \(v\) represents an equivalence class of substrings that all end in exactly the same positions in \(C_n\). Let \(M(v)\) be the maximum length represented by state \(v\). If the suffix link of \(v\) points to \(u\), then the represented lengths form the interval
$$M(u)+1,\ M(u)+2,\ \dots,\ M(v).$$
So every distinct substring belongs to exactly one state, and within that state the longest candidate has length \(M(v)\). For a string of length \(n\), a suffix automaton has at most \(2n-1\) states, which is why the whole repeated-substring structure can be stored in linear size.
While the automaton is built online from left to right, each newly created non-clone state corresponds to one new suffix ending at the current position, so it starts with one end position. Clone states start from zero because they only split structure; they do not introduce a new occurrence by themselves.
After the full word has been inserted, the states are processed in decreasing order of \(M(v)\). When a state \(v\) contributes its total to its suffix-link parent, all longer substrings have already been counted, so the propagated value becomes the size of the end-position set for that entire class. Denoting this final count by \(R(v)\), every substring represented by \(v\) occurs exactly \(R(v)\) times in \(C_n\).
This count automatically includes overlapping repetitions, because different end positions are counted separately even if the corresponding substring occurrences overlap in the word.
Fix a state \(v\). Every substring represented by \(v\) occurs exactly \(R(v)\) times, but those substrings have several possible lengths inside the interval described above. For the quantity \(L_n(k)\), only the longest one matters, because among all substrings with the same repetition count we want the maximum possible length. Therefore state \(v\) contributes the candidate length \(M(v)\) to the bucket for the exact repetition count \(R(v)\).
If \(B(t)\) denotes the largest substring length seen among states with exact occurrence count \(t\), we update
$$B(R(v))=\max\bigl(B(R(v)),M(v)\bigr).$$
But the problem asks for “at least \(k\) times”, not “exactly \(k\) times”. So we transform exact counts into lower bounds by a suffix maximum:
$$L_n(k)=\max_{t\ge k} B(t).$$
A single pass from right to left over the array of counts computes all values \(L_n(1),L_n(2),\dots,L_n(n)\).
Once the entire array \(L_n(k)\) is known, the required answer is simply
$$S_n=\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k).$$
The sequence \(L_n(k)\) is non-increasing in \(k\): requiring more repetitions can never make the best repeated substring longer. Hence after the first zero appears, all later terms are also zero, so the final accumulation is straightforward.
For \(i=0,1,\dots,9\), the two source sequences are
$$a_i=(0,1,1,0,1,0,0,1,1,0),$$
$$b_i=(0,1,0,1,1,0,1,0,1,1).$$
Taking bitwise XOR gives
$$C_{10}=0011001101.$$
Now inspect repeated substrings:
\(L_{10}(1)=10\) because the whole word appears once. The substring \(00110\) appears twice, at positions \(1\) through \(5\) and \(5\) through \(9\) in one-based indexing, so \(L_{10}(2)=5\). The substring \(01\) appears three times, and no substring of length \(3\) appears three times, so \(L_{10}(3)=2\). Finally, single symbols appear five times each, giving \(L_{10}(4)=L_{10}(5)=1\), and for \(k\ge 6\) the value is \(0\).
Therefore
$$L_{10}(k)=(10,5,2,1,1,0,\dots),$$
and the sum of positive terms is
$$10+5+2+1+1=19.$$
This agrees with the small checkpoints used by the implementation, in particular \(L_{10}(2)=5\) and \(L_{10}(3)=2\).
The C++, Python, and Java implementations generate the bits of \(C_n\) on the fly, so no separate quadratic substring table is ever materialized. Each new bit extends a suffix automaton over the binary alphabet \(\{0,1\}\); because the alphabet has size two, every state needs only two outgoing transitions, one suffix link, one maximum-length field, and one occurrence counter.
After the automaton is complete, the implementation counting-sorts states by their represented maximum length, then walks that order from longest to shortest so occurrence totals can be pushed through suffix links. Next it records, for each exact occurrence count, the largest maximum length attained by any state with that count. A backward suffix-maximum pass converts those exact-count buckets into the desired values \(L_n(k)\). The last step sums the positive entries and stops once they become zero.
Let \(n\) be the length of the word. Building the binary sequence and extending the suffix automaton are both linear, and the automaton contains at most \(2n-1\) states. Sorting states by length with counting sort is \(O(n)\), propagating occurrence counts is \(O(n)\), and the final exact-count and suffix-maximum passes are also \(O(n)\). Thus the total running time is \(O(n)\), and the memory usage is \(O(n)\).
Für \(0 \le i \lt n\) seien
$$a_i=\operatorname{popcount}(i)\bmod 2,\qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor-\left\lfloor\frac{i}{\varphi}\right\rfloor,\qquad c_i=a_i\oplus b_i,$$
wobei \(\varphi=\frac{1+\sqrt{5}}{2}\) der goldene Schnitt ist. Daraus entsteht das Binärwort
$$C_n=c_0c_1\dots c_{n-1}.$$
Für jedes \(k\ge 1\) sei \(L_n(k)\) die maximale Länge eines Teilstrings von \(C_n\), der mindestens \(k\)-mal vorkommt; Überlappungen sind erlaubt. Gesucht ist
$$\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
für \(n=5{,}000{,}000\). Da es quadratisch viele Teilstring-Intervalle gibt, muss die Lösung die Wiederholungsstruktur des Wortes komprimieren statt alle Kandidaten einzeln zu prüfen.
Sobald \(C_n\) feststeht, ist die Aufgabe eine reine Häufigkeitsfrage über Teilstrings eines einzigen Binärworts. Das passende Werkzeug ist ein Suffixautomat, weil er alle verschiedenen Teilstrings in linearer Größe zusammenfasst und zugleich genug Information liefert, um ihre Vorkommenszahlen zu rekonstruieren.
Der erste Anteil \(a_i\) ist die Parität der Anzahl von \(1\)-Bits in der Binärdarstellung von \(i\); das ist genau das Thue-Morse-Bit an Position \(i\). Der zweite Anteil \(b_i\) ist eine Beatty-Differenz. Weil \(\frac{1}{\varphi}=\varphi-1\in(0,1)\) gilt, kann die Folge
$$\left\lfloor\frac{i}{\varphi}\right\rfloor$$
beim Übergang von \(i\) zu \(i+1\) höchstens um \(1\) wachsen. Deshalb ist
$$b_i\in\{0,1\}.$$
Damit bleibt auch \(c_i=a_i\oplus b_i\) binär. Das eigentliche Eingabewort der String-Aufgabe ist also schlicht \(C_n\), und seine Erzeugung kostet nur \(O(n)\) Zeit.
Ein Suffixautomat gruppiert Teilstrings nach ihrer Menge von Endpositionen. Jeder Zustand \(v\) steht für eine Äquivalenzklasse von Teilstrings, die in \(C_n\) genau an denselben Endpositionen enden. Sei \(M(v)\) die größte von \(v\) repräsentierte Länge. Zeigt der Suffix-Link von \(v\) auf \(u\), dann bilden die repräsentierten Längen das Intervall
$$M(u)+1,\ M(u)+2,\ \dots,\ M(v).$$
Somit gehört jeder verschiedene Teilstring genau zu einem Zustand, und innerhalb dieses Zustands ist der längste Kandidat gerade \(M(v)\). Für ein Wort der Länge \(n\) hat ein Suffixautomat höchstens \(2n-1\) Zustände; genau das macht die Struktur linear groß.
Beim inkrementellen Aufbau von links nach rechts entspricht jeder neu erzeugte Nicht-Klon-Zustand einem neuen Suffix, der an der aktuellen Position endet; deshalb startet er mit genau einer Endposition. Klon-Zustände beginnen mit null, denn sie teilen nur bestehende Struktur auf, erzeugen aber kein neues Vorkommen.
Nachdem das gesamte Wort eingefügt wurde, verarbeitet man die Zustände in absteigender Reihenfolge von \(M(v)\). Wenn ein Zustand \(v\) seine Gesamtzahl an seinen Suffix-Link-Vorgänger weitergibt, sind alle längeren Teilstrings bereits berücksichtigt. Der propagierte Wert wird so zur Größe der Endpositionsmenge dieser Klasse. Bezeichnen wir diesen Endwert mit \(R(v)\), dann kommt jeder von \(v\) repräsentierte Teilstring genau \(R(v)\)-mal in \(C_n\) vor.
Überlappende Vorkommen werden automatisch mitgezählt, weil unterschiedliche Endpositionen separat gezählt werden, auch wenn sich die zugehörigen Intervalle im Wort überschneiden.
Fixiere einen Zustand \(v\). Alle von \(v\) repräsentierten Teilstrings treten genau \(R(v)\)-mal auf, aber ihre Längen variieren innerhalb des obigen Intervalls. Für \(L_n(k)\) interessiert nur der längste davon, denn unter allen Teilstrings mit derselben Wiederholungszahl zählt nur die maximale Länge. Daher liefert Zustand \(v\) den Kandidaten \(M(v)\) für den exakten Wiederholungswert \(R(v)\).
Bezeichne \(B(t)\) als die größte beobachtete Teilstringlänge unter allen Zuständen mit exakt \(t\) Vorkommen. Dann wird aktualisiert durch
$$B(R(v))=\max\bigl(B(R(v)),M(v)\bigr).$$
Gesucht ist aber „mindestens \(k\)-mal“ statt „genau \(k\)-mal“. Deshalb folgt durch ein Suffixmaximum
$$L_n(k)=\max_{t\ge k} B(t).$$
Ein einziger Durchlauf von rechts nach links über die Zählarray-Indizes liefert also alle Werte \(L_n(1),L_n(2),\dots,L_n(n)\).
Sind alle \(L_n(k)\) bekannt, dann ist die gesuchte Zahl schlicht
$$S_n=\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k).$$
Die Folge \(L_n(k)\) ist monoton nicht steigend: Wenn man mehr Wiederholungen fordert, kann der beste Teilstring nicht länger werden. Sobald also der erste Nullwert erscheint, sind alle späteren Werte ebenfalls null.
Für \(i=0,1,\dots,9\) erhält man
$$a_i=(0,1,1,0,1,0,0,1,1,0),$$
$$b_i=(0,1,0,1,1,0,1,0,1,1).$$
Das XOR ergibt
$$C_{10}=0011001101.$$
Nun betrachten wir Wiederholungen: \(L_{10}(1)=10\), weil das ganze Wort einmal vorkommt. Der Teilstring \(00110\) erscheint zweimal, nämlich an den Positionen \(1\) bis \(5\) und \(5\) bis \(9\) in einsbasierter Zählung; also ist \(L_{10}(2)=5\). Der Teilstring \(01\) kommt dreimal vor, und kein Teilstring der Länge \(3\) kommt dreimal vor, also gilt \(L_{10}(3)=2\). Außerdem treten die einzelnen Symbole jeweils fünfmal auf, daher \(L_{10}(4)=L_{10}(5)=1\); für \(k\ge 6\) ist der Wert \(0\).
Damit
$$L_{10}(k)=(10,5,2,1,1,0,\dots),$$
und die Summe der positiven Terme ist
$$10+5+2+1+1=19.$$
Das stimmt mit den kleinen Kontrollwerten der Implementierung überein, insbesondere mit \(L_{10}(2)=5\) und \(L_{10}(3)=2\).
Die C++-, Python- und Java-Implementierungen erzeugen die Bits von \(C_n\) fortlaufend, ohne jemals eine quadratische Teilstringtabelle anzulegen. Jedes neue Bit erweitert einen Suffixautomaten über dem Alphabet \(\{0,1\}\); wegen des binären Alphabets benötigt jeder Zustand nur zwei ausgehende Übergänge, einen Suffix-Link, eine maximale Repräsentationslänge und einen Zähler für Endpositionen.
Nach dem vollständigen Aufbau werden die Zustände per Counting Sort nach ihrer maximal repräsentierten Länge geordnet und von lang nach kurz verarbeitet, damit die Vorkommenszahlen korrekt über die Suffix-Links nach oben propagiert werden. Anschließend speichert die Implementierung für jede exakte Vorkommenszahl die größte von einem Zustand erreichte Länge. Ein rückwärts laufendes Suffixmaximum macht daraus die gesuchten Werte \(L_n(k)\). Zum Schluss werden die positiven Terme aufsummiert; nach dem ersten Nullwert kann der Prozess abbrechen.
Sei \(n\) die Länge des Wortes. Das Erzeugen der Bits und das Erweitern des Suffixautomaten sind linear, und der Automat besitzt höchstens \(2n-1\) Zustände. Das Sortieren der Zustände nach Länge per Counting Sort kostet \(O(n)\), die Propagation der Vorkommenszahlen ebenfalls \(O(n)\), und die anschließenden Durchläufe über die Zählarrays sind wieder linear. Insgesamt ergibt sich also Laufzeit \(O(n)\) bei Speicherbedarf \(O(n)\).
\(0 \le i \lt n\) için
$$a_i=\operatorname{popcount}(i)\bmod 2,\qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor-\left\lfloor\frac{i}{\varphi}\right\rfloor,\qquad c_i=a_i\oplus b_i$$
tanımlansın; burada \(\varphi=\frac{1+\sqrt{5}}{2}\) altın orandır. İncelenen ikili kelime
$$C_n=c_0c_1\dots c_{n-1}$$
şeklindedir. Her \(k\ge 1\) için \(L_n(k)\), \(C_n\) içinde en az \(k\) kez geçen en uzun alt dizgenin uzunluğudur; örtüşen tekrarlar da sayılır. Hesaplanması gereken değer
$$\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
olup burada \(n=5{,}000{,}000\)'dır. Milyonlarca karakter için tüm alt dizgeleri tek tek kontrol etmek mümkün olmadığından, çözüm tekrar yapısını sıkıştıran doğrusal bir yöntem kullanır.
\(C_n\) üretildikten sonra problem, tek bir ikili kelimenin alt dizgelerinin kaç kez tekrarlandığını bulma problemine dönüşür. Bunun için en uygun araç suffix automaton'dır; çünkü tüm farklı alt dizgeleri doğrusal boyutta toplar ve her bir sınıfın kaç kez göründüğünü geri çıkarmaya izin verir.
İlk parça olan \(a_i\), \(i\)'nin ikili yazımındaki \(1\) bitlerinin sayısının paritesidir; yani Thue-Morse dizisinin \(i\). bitidir. İkinci parça olan \(b_i\) ise bir Beatty farkıdır. \(\frac{1}{\varphi}=\varphi-1\in(0,1)\) olduğundan
$$\left\lfloor\frac{i}{\varphi}\right\rfloor$$
dizisi \(i\) bir arttığında en fazla \(1\) artabilir. Bu yüzden
$$b_i\in\{0,1\}$$
olur. Dolayısıyla \(c_i=a_i\oplus b_i\) yine ikilidir ve string problemine giren veri doğrudan \(C_n\) kelimesidir. Bu kelime tek geçişte \(O(n)\) zamanda üretilebilir.
Bir suffix automaton, alt dizgeleri bitiş konumları kümesine göre gruplar. Her \(v\) durumu, \(C_n\) içinde tam olarak aynı bitiş noktalarına sahip bir alt dizge eşdeğerlik sınıfını temsil eder. \(M(v)\), bu durumun temsil ettiği en büyük uzunluk olsun. \(v\)'nin suffix link'i \(u\)'ya gidiyorsa, bu durumda temsil edilen uzunluklar
$$M(u)+1,\ M(u)+2,\ \dots,\ M(v)$$
aralığını oluşturur. Böylece her farklı alt dizge tam olarak bir duruma aittir ve o durum içindeki en uzun adayın uzunluğu \(M(v)\)'dir. Uzunluğu \(n\) olan bir kelime için suffix automaton en fazla \(2n-1\) durum içerir; doğrusal alan avantajı buradan gelir.
Automaton soldan sağa çevrimiçi kurulurken, yeni oluşan klon olmayan her durum o anda sona eren yeni bir suffix'e karşılık gelir; bu yüzden başlangıçta bir bitiş konumuna sahiptir. Klon durumlar ise sadece yapıyı ayırdığı için sıfırdan başlar; kendi başına yeni bir gerçekleşme eklemez.
Tüm kelime eklendikten sonra durumlar \(M(v)\) değerine göre büyükten küçüğe işlenir. Bir \(v\) durumu toplamını suffix link ebeveynine aktardığında, daha uzun sınıfların hepsi önceden sayılmış olur. Sonuçta elde edilen değer, o durumun end-position kümesinin büyüklüğüdür. Bu nihai sayıya \(R(v)\) dersek, \(v\)'nin temsil ettiği her alt dizge \(C_n\) içinde tam olarak \(R(v)\) kez görünür.
Bu sayım örtüşen tekrarları doğal olarak kapsar; çünkü alt dizgeler örtüşse bile farklı bitiş konumları ayrı ayrı sayılır.
Sabit bir \(v\) durumu için temsil edilen tüm alt dizgeler aynı \(R(v)\) kadar tekrar eder, fakat uzunlukları yukarıdaki aralık içinde değişebilir. \(L_n(k)\) için önemli olan yalnızca en uzun olandır; çünkü aynı tekrar sayısına sahip alt dizgeler arasında maksimum uzunluğu arıyoruz. Bu nedenle \(v\) durumu, tam tekrar sayısı \(R(v)\) olan kova için \(M(v)\) adayını verir.
\(B(t)\), tam olarak \(t\) kez görünen alt dizgeler arasında görülen en büyük uzunluk olsun. O zaman
$$B(R(v))=\max\bigl(B(R(v)),M(v)\bigr)$$
güncellemesi yapılır. Fakat problem “tam \(k\)” değil, “en az \(k\)” ister. Bu yüzden sağdan sola suffix maksimum alınır:
$$L_n(k)=\max_{t\ge k} B(t).$$
Tek bir sağdan sola tarama ile \(L_n(1),L_n(2),\dots,L_n(n)\) değerlerinin tamamı elde edilir.
Tüm \(L_n(k)\) değerleri bulunduktan sonra cevap
$$S_n=\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
şeklindedir. \(L_n(k)\) dizisi \(k\)'ye göre azalmayandır; daha fazla tekrar istemek en iyi alt dizgeyi uzatamaz. Bu yüzden ilk sıfırdan sonra gelen bütün terimler de sıfır olur ve son toplama basitleşir.
\(i=0,1,\dots,9\) için kaynak diziler
$$a_i=(0,1,1,0,1,0,0,1,1,0),$$
$$b_i=(0,1,0,1,1,0,1,0,1,1)$$
olur. XOR alınca
$$C_{10}=0011001101$$
elde edilir. Şimdi tekrarları inceleyelim: Tüm kelime bir kez geçtiği için \(L_{10}(1)=10\). \(00110\) alt dizgesi biri \(1\) ile \(5\), diğeri \(5\) ile \(9\) arasında olmak üzere iki kez geçer; dolayısıyla \(L_{10}(2)=5\). \(01\) alt dizgesi üç kez görünür ve uzunluğu \(3\) olan hiçbir alt dizge üç kez görünmez; bu nedenle \(L_{10}(3)=2\). Tek karakterler ise beşer kez göründüğünden \(L_{10}(4)=L_{10}(5)=1\) olur. \(k\ge 6\) için değer sıfırdır.
Sonuç olarak
$$L_{10}(k)=(10,5,2,1,1,0,\dots)$$
ve pozitif terimlerin toplamı
$$10+5+2+1+1=19$$
çıkar. Bu, uygulamadaki küçük kontrol değerleriyle, özellikle de \(L_{10}(2)=5\) ve \(L_{10}(3)=2\) ile tam uyumludur.
C++, Python ve Java implementasyonları \(C_n\) bitlerini akış halinde üretir; ayrı bir alt dizge matrisi tutulmaz. Her yeni bit, \(\{0,1\}\) alfabesi üzerindeki bir suffix automaton'ı standart biçimde genişletir. Alfabe ikili olduğu için her durumda yalnızca iki geçiş, bir suffix link, temsil edilen en büyük uzunluk ve bir tekrar sayacı yeterlidir.
Automaton tamamlandıktan sonra durumlar temsil ettikleri maksimum uzunluğa göre counting sort ile sıralanır ve uzun olandan kısa olana doğru işlenir. Böylece tekrar sayıları suffix link'ler boyunca doğru yönde toplanır. Ardından implementasyon, her tam tekrar sayısı için ulaşılan en büyük uzunluğu kaydeder. Sağdan sola alınan bir suffix maksimum, bu “tam sayı” kovalarını doğrudan \(L_n(k)\) değerlerine çevirir. Son aşamada pozitif terimler toplanır ve ilk sıfırdan sonra işlem durdurulur.
\(n\) kelime uzunluğu olsun. Bitleri üretmek ve suffix automaton'ı kurmak doğrusal zamandadır; automaton en fazla \(2n-1\) durum içerir. Durumları uzunluğa göre counting sort ile sıralamak \(O(n)\), tekrar sayılarını suffix link boyunca yaymak \(O(n)\), son iki dizi taraması da \(O(n)\) zaman alır. Bu nedenle toplam zaman karmaşıklığı \(O(n)\), bellek karmaşıklığı \(O(n)\)'dir.
Para \(0 \le i \lt n\), definimos
$$a_i=\operatorname{popcount}(i)\bmod 2,\qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor-\left\lfloor\frac{i}{\varphi}\right\rfloor,\qquad c_i=a_i\oplus b_i,$$
donde \(\varphi=\frac{1+\sqrt{5}}{2}\). La palabra binaria estudiada es
$$C_n=c_0c_1\dots c_{n-1}.$$
Para cada \(k\ge 1\), \(L_n(k)\) es la longitud máxima de una subcadena de \(C_n\) que aparece al menos \(k\) veces, permitiendo solapamientos. Hay que calcular
$$\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
para \(n=5{,}000{,}000\). Como hay millones de posiciones y cuadráticamente muchas subcadenas candidatas, la solución debe comprimir la estructura de repeticiones en vez de inspeccionar cada intervalo por separado.
Una vez construido \(C_n\), el problema pasa a ser una cuestión de frecuencias de subcadenas dentro de una única cadena binaria. La herramienta adecuada es el autómata de sufijos, porque representa todas las subcadenas distintas en espacio lineal y además permite reconstruir cuántas veces aparece cada clase.
El término \(a_i\) es la paridad del número de bits \(1\) en la expansión binaria de \(i\); es decir, el bit de Thue-Morse en la posición \(i\). El término \(b_i\) es una diferencia de Beatty. Como \(\frac{1}{\varphi}=\varphi-1\in(0,1)\), la sucesión
$$\left\lfloor\frac{i}{\varphi}\right\rfloor$$
solo puede aumentar en \(0\) o en \(1\) al pasar de \(i\) a \(i+1\). Por eso
$$b_i\in\{0,1\}.$$
En consecuencia, \(c_i=a_i\oplus b_i\) vuelve a ser binario y el dato real del problema de cadenas es simplemente la palabra \(C_n\). Generarla cuesta \(O(n)\) tiempo.
Un autómata de sufijos agrupa subcadenas según su conjunto de posiciones finales. Cada estado \(v\) representa una clase de equivalencia de subcadenas que terminan exactamente en las mismas posiciones de \(C_n\). Sea \(M(v)\) la longitud máxima representada por \(v\). Si el sufijo-enlace de \(v\) apunta a \(u\), entonces las longitudes representadas forman el intervalo
$$M(u)+1,\ M(u)+2,\ \dots,\ M(v).$$
Así, cada subcadena distinta pertenece a un único estado, y dentro de ese estado la candidata más larga tiene longitud \(M(v)\). Para una cadena de longitud \(n\), el autómata de sufijos tiene como máximo \(2n-1\) estados, lo que explica el uso de memoria lineal.
Durante la construcción en línea, cada nuevo estado no clonado corresponde a un nuevo sufijo que termina en la posición actual, así que empieza con una única posición final. Los estados clonados empiezan con cero, porque solo dividen estructura ya existente y no crean por sí mismos una ocurrencia nueva.
Después de insertar la palabra completa, los estados se procesan en orden decreciente de \(M(v)\). Cuando un estado \(v\) transfiere su total a su padre por sufijo-enlace, todas las clases más largas ya han sido acumuladas. El valor resultante pasa a ser el tamaño del conjunto de posiciones finales de esa clase. Si llamamos \(R(v)\) a ese conteo final, cualquier subcadena representada por \(v\) aparece exactamente \(R(v)\) veces en \(C_n\).
Este conteo incluye repeticiones solapadas de forma natural, porque posiciones finales distintas se cuentan por separado aunque los intervalos de ocurrencia compartan caracteres.
Fijemos un estado \(v\). Todas sus subcadenas representadas aparecen exactamente \(R(v)\) veces, pero sus longitudes varían dentro del intervalo del estado. Para \(L_n(k)\) solo importa la más larga, porque buscamos la longitud máxima entre todas las subcadenas con esa frecuencia. Por tanto, el estado \(v\) aporta el candidato \(M(v)\) al cajón del conteo exacto \(R(v)\).
Si \(B(t)\) denota la mayor longitud observada entre estados con exactamente \(t\) apariciones, la actualización es
$$B(R(v))=\max\bigl(B(R(v)),M(v)\bigr).$$
Pero el problema pide “al menos \(k\) veces”, no “exactamente \(k\) veces”. Por eso se aplica un máximo sufijo:
$$L_n(k)=\max_{t\ge k} B(t).$$
Una sola pasada de derecha a izquierda sobre los conteos produce todos los valores \(L_n(1),L_n(2),\dots,L_n(n)\).
Una vez conocido todo el arreglo \(L_n(k)\), la respuesta buscada es
$$S_n=\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k).$$
La sucesión \(L_n(k)\) es no creciente con respecto a \(k\): pedir más repeticiones nunca puede alargar la mejor subcadena repetida. Por ello, tras el primer cero, todos los términos posteriores también son cero.
Para \(i=0,1,\dots,9\), las dos secuencias base son
$$a_i=(0,1,1,0,1,0,0,1,1,0),$$
$$b_i=(0,1,0,1,1,0,1,0,1,1).$$
Su XOR da
$$C_{10}=0011001101.$$
Ahora observamos las repeticiones: \(L_{10}(1)=10\) porque la palabra completa aparece una vez. La subcadena \(00110\) aparece dos veces, en las posiciones \(1\) a \(5\) y \(5\) a \(9\) usando índices basados en \(1\); por tanto \(L_{10}(2)=5\). La subcadena \(01\) aparece tres veces, y ninguna subcadena de longitud \(3\) aparece tres veces, así que \(L_{10}(3)=2\). Además, los símbolos individuales aparecen cinco veces cada uno, lo que da \(L_{10}(4)=L_{10}(5)=1\). Para \(k\ge 6\), el valor ya es \(0\).
Por consiguiente,
$$L_{10}(k)=(10,5,2,1,1,0,\dots),$$
y la suma de los términos positivos vale
$$10+5+2+1+1=19.$$
Esto coincide con los pequeños puntos de control de la implementación, en particular \(L_{10}(2)=5\) y \(L_{10}(3)=2\).
Las implementaciones en C++, Python y Java generan los bits de \(C_n\) en línea, sin materializar nunca una tabla cuadrática de subcadenas. Cada nuevo bit extiende un autómata de sufijos sobre el alfabeto binario \(\{0,1\}\); como el alfabeto tiene solo dos símbolos, cada estado necesita únicamente dos transiciones salientes, un sufijo-enlace, una longitud máxima representada y un contador de ocurrencias.
Una vez construido el autómata, la implementación ordena los estados por longitud máxima mediante counting sort y los recorre de mayor a menor para propagar correctamente los conteos por los sufijo-enlaces. Después registra, para cada número exacto de apariciones, la mayor longitud alcanzada por algún estado con ese conteo. Un pase de máximos sufijo convierte esos valores exactos en los \(L_n(k)\) pedidos. Finalmente se suman los términos positivos y se detiene el proceso cuando aparecen ceros.
Sea \(n\) la longitud de la palabra. Generar los bits y extender el autómata de sufijos es lineal, y el autómata contiene a lo sumo \(2n-1\) estados. Ordenar por longitud con counting sort cuesta \(O(n)\), propagar los conteos también cuesta \(O(n)\), y los recorridos finales sobre los arreglos de conteos son igualmente lineales. En conjunto, el algoritmo corre en \(O(n)\) tiempo y usa \(O(n)\) memoria.
对 \(0 \le i \lt n\)，定义
$$a_i=\operatorname{popcount}(i)\bmod 2,\qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor-\left\lfloor\frac{i}{\varphi}\right\rfloor,\qquad c_i=a_i\oplus b_i,$$
其中 \(\varphi=\frac{1+\sqrt{5}}{2}\)。由此得到二进制串
$$C_n=c_0c_1\dots c_{n-1}.$$
对每个 \(k\ge 1\)，记 \(L_n(k)\) 为“在 \(C_n\) 中至少出现 \(k\) 次的最长子串长度”，这里允许出现位置彼此重叠。题目要求计算
$$\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
在 \(n=5{,}000{,}000\) 时的值。由于长度达到五百万时，子串区间的数量是二次级别，任何直接枚举所有子串的方法都不可行，必须把重复结构整体压缩起来处理。
一旦二进制串 \(C_n\) 被构造出来，问题就变成了“一个固定字符串里，各种不同子串分别出现多少次”。最合适的工具是后缀自动机，因为它能用线性空间表示所有不同子串，并且还保留了恢复出现次数所需的信息。
\(a_i\) 是整数 \(i\) 的二进制表示中 \(1\) 的个数的奇偶性，也就是 Thue-Morse 序列在位置 \(i\) 的值。\(b_i\) 则是一个 Beatty 差分。由于
$$\frac{1}{\varphi}=\varphi-1\in(0,1),$$
所以序列
$$\left\lfloor\frac{i}{\varphi}\right\rfloor$$
在 \(i\) 增加 \(1\) 时最多只会上升 \(1\)。因此
$$b_i\in\{0,1\}.$$
于是 \(c_i=a_i\oplus b_i\) 仍然是二进制位，整个字符串问题的输入就是单纯的二进制串 \(C_n\)。按顺序生成这些字符只需要 \(O(n)\) 时间。
后缀自动机按“结束位置集合”对不同子串分组。每个状态 \(v\) 都对应一类子串，它们在 \(C_n\) 中恰好拥有相同的结束位置集合。设 \(M(v)\) 是状态 \(v\) 所表示的最大长度。如果 \(v\) 的后缀链接指向状态 \(u\)，那么这个状态覆盖的所有长度就是
$$M(u)+1,\ M(u)+2,\ \dots,\ M(v).$$
换句话说，每一个不同子串都恰好落在一个状态里，而在这个状态中最长的那个子串长度就是 \(M(v)\)。对长度为 \(n\) 的字符串，后缀自动机的状态数最多是 \(2n-1\)，这正是它能在线性空间中承载全部子串信息的原因。
自动机按字符从左到右在线构造。每加入一个新字符，产生的新非克隆状态对应一个新的后缀，它以当前位置为结束点，因此初始时带有一个结束位置。克隆状态的初始计数为零，因为它只是为了拆分已有结构，并没有单独创造新的出现。
当整串构造完成后，将所有状态按 \(M(v)\) 从大到小处理。某个状态 \(v\) 把自己的总数传给后缀链接父状态时，所有更长的类都已经先被累加完毕，因此传播后的值就会变成该状态对应结束位置集合的大小。把这个最终值记作 \(R(v)\)，则状态 \(v\) 所代表的任意子串在 \(C_n\) 中都恰好出现 \(R(v)\) 次。
这种计数天然包含重叠出现，因为即便两个子串区间彼此重叠，只要它们的结束位置不同，就会被分别计入。
固定一个状态 \(v\)。这个状态表示的一整类子串都出现了同样多次，即 \(R(v)\) 次，但它们的长度在上面的区间中可以变化。对于 \(L_n(k)\) 来说，真正重要的只有这一类里最长的那个子串，因为我们最终关心的是在满足重复次数条件的所有子串中，长度最大的那一个。所以状态 \(v\) 只需要把候选值 \(M(v)\) 贡献给“恰好出现 \(R(v)\) 次”这一桶。
如果用 \(B(t)\) 表示“恰好出现 \(t\) 次的所有状态里，能得到的最大子串长度”，那么更新规则就是
$$B(R(v))=\max\bigl(B(R(v)),M(v)\bigr).$$
但题目要的是“至少出现 \(k\) 次”，不是“恰好出现 \(k\) 次”。因此还要对这个数组做一次后缀最大化：
$$L_n(k)=\max_{t\ge k} B(t).$$
只要从右向左扫一遍出现次数数组，就能一次性得到全部 \(L_n(1),L_n(2),\dots,L_n(n)\)。
当所有 \(L_n(k)\) 都求出来以后，目标答案就是
$$S_n=\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k).$$
由于重复次数要求越高，可行的最长子串只会更短或者不变，所以 \(L_n(k)\) 关于 \(k\) 是单调不增的。也就是说，一旦某个 \(k\) 的值已经变成 \(0\)，后面的所有值都会继续是 \(0\)，最终求和就很直接了。
当 \(i=0,1,\dots,9\) 时，两条基础序列分别为
$$a_i=(0,1,1,0,1,0,0,1,1,0),$$
$$b_i=(0,1,0,1,1,0,1,0,1,1).$$
逐位异或后得到
$$C_{10}=0011001101.$$
现在来看重复子串。整串本身出现一次，因此 \(L_{10}(1)=10\)。子串 \(00110\) 出现了两次，若用从 \(1\) 开始的下标，则位置分别是 \(1\) 到 \(5\) 与 \(5\) 到 \(9\)，所以 \(L_{10}(2)=5\)。子串 \(01\) 出现了三次，而长度为 \(3\) 的子串没有任何一个能出现三次，因此 \(L_{10}(3)=2\)。另外，单个字符 \(0\) 和 \(1\) 都各出现五次，于是 \(L_{10}(4)=L_{10}(5)=1\)。对所有 \(k\ge 6\)，值都已经变成 \(0\)。
因此
$$L_{10}(k)=(10,5,2,1,1,0,\dots),$$
正项之和为
$$10+5+2+1+1=19.$$
这与实现中的小规模校验完全一致，尤其是 \(L_{10}(2)=5\) 和 \(L_{10}(3)=2\)。
C++、Python 和 Java 实现都会一边生成 \(C_n\) 的字符，一边扩展后缀自动机，因此从头到尾都不会构造任何二次规模的子串表。由于字母表只有 \(\{0,1\}\) 两个符号，每个状态只需要保存两个转移、一个后缀链接、一个最大表示长度以及一个出现次数计数器。
自动机构造结束后，程序先按状态的最大表示长度进行计数排序，再从长到短遍历这些状态，把出现次数沿后缀链接向上累加。接着，用一个按“精确出现次数”索引的数组记录每个计数下能达到的最大长度。再做一次从右向左的后缀最大化，就把“恰好出现多少次”转成了题目真正需要的“至少出现多少次”。最后只需把所有正的 \(L_n(k)\) 累加起来，并在遇到第一个零后停止即可。
设字符串长度为 \(n\)。生成二进制串并扩展后缀自动机都是线性的，且自动机状态数最多为 \(2n-1\)。按长度的计数排序需要 \(O(n)\) 时间，沿后缀链接传播出现次数是 \(O(n)\)，后面的两次数组扫描也都是 \(O(n)\)。因此总时间复杂度是 \(O(n)\)，空间复杂度也是 \(O(n)\)。
Для \(0 \le i \lt n\) задаются
$$a_i=\operatorname{popcount}(i)\bmod 2,\qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor-\left\lfloor\frac{i}{\varphi}\right\rfloor,\qquad c_i=a_i\oplus b_i,$$
где \(\varphi=\frac{1+\sqrt{5}}{2}\). Из этих битов строится бинарная строка
$$C_n=c_0c_1\dots c_{n-1}.$$
Для каждого \(k\ge 1\) величина \(L_n(k)\) означает максимальную длину подстроки \(C_n\), которая встречается не менее \(k\) раз; перекрывающиеся вхождения тоже разрешены. Требуется вычислить
$$\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
при \(n=5{,}000{,}000\). Поскольку число возможных подстрочных интервалов квадратично, прямой перебор невозможен, и решение должно сжимать структуру повторов целиком.
После построения строки \(C_n\) задача превращается в вопрос о частотах различных подстрок внутри одной фиксированной бинарной строки. Главный инструмент здесь — суффиксный автомат, потому что он хранит все различные подстроки в линейном размере и одновременно позволяет восстановить, сколько раз встречается каждый класс.
Величина \(a_i\) — это четность числа единичных битов в двоичной записи \(i\), то есть бит последовательности Тюэ-Морса в позиции \(i\). Величина \(b_i\) — разность Beatty. Поскольку
$$\frac{1}{\varphi}=\varphi-1\in(0,1),$$
последовательность
$$\left\lfloor\frac{i}{\varphi}\right\rfloor$$
при увеличении \(i\) на единицу может возрасти не более чем на \(1\). Поэтому
$$b_i\in\{0,1\}.$$
Следовательно, и \(c_i=a_i\oplus b_i\) остается бинарным битом, а весь вход в строковую часть задачи — это просто бинарная строка \(C_n\). Ее можно породить за \(O(n)\) времени.
Суффиксный автомат группирует подстроки по множеству их конечных позиций. Каждый его статус \(v\) соответствует классу эквивалентности подстрок, которые заканчиваются в \(C_n\) ровно в одном и том же наборе позиций. Обозначим через \(M(v)\) максимальную длину, представляемую состоянием \(v\). Если суффиксная ссылка из \(v\) ведет в \(u\), то диапазон длин этого состояния равен
$$M(u)+1,\ M(u)+2,\ \dots,\ M(v).$$
Значит, каждая различная подстрока принадлежит ровно одному состоянию, а самая длинная подстрока этого класса имеет длину \(M(v)\). Для строки длины \(n\) суффиксный автомат содержит не более \(2n-1\) состояний, и именно поэтому он остается линейным по памяти.
Во время онлайн-построения каждый новый неклонированный статус соответствует новому суффиксу, оканчивающемуся в текущей позиции, поэтому его начальный вклад равен одной конечной позиции. Клоны стартуют с нуля: они лишь разделяют уже существующую структуру, но сами по себе не добавляют нового вхождения.
После того как вся строка вставлена, состояния обрабатываются в порядке убывания \(M(v)\). Когда состояние \(v\) передает свой накопленный счетчик по суффиксной ссылке наверх, все более длинные классы уже учтены. В результате это значение становится мощностью множества конечных позиций данного класса. Обозначим итоговый счетчик через \(R(v)\). Тогда любая подстрока, представляемая состоянием \(v\), встречается в \(C_n\) ровно \(R(v)\) раз.
Такой способ автоматически учитывает перекрывающиеся повторения, потому что разные конечные позиции считаются отдельно даже тогда, когда интервалы вхождений пересекаются.
Зафиксируем состояние \(v\). Все подстроки внутри этого состояния встречаются одинаковое число раз, а именно \(R(v)\), но их длины могут быть разными в пределах интервала состояния. Для функции \(L_n(k)\) важна только максимальная длина в этом классе, потому что среди всех подстрок с данным числом повторений нас интересует самая длинная. Поэтому от состояния \(v\) нужен только кандидат \(M(v)\) для корзины точного числа вхождений \(R(v)\).
Если \(B(t)\) обозначает максимальную длину среди состояний, встречающихся ровно \(t\) раз, то выполняется обновление
$$B(R(v))=\max\bigl(B(R(v)),M(v)\bigr).$$
Но по условию нужно “не менее \(k\) раз”, а не “ровно \(k\) раз”. Поэтому далее берется суффиксный максимум:
$$L_n(k)=\max_{t\ge k} B(t).$$
Один проход справа налево по массиву частот дает сразу все значения \(L_n(1),L_n(2),\dots,L_n(n)\).
Когда массив \(L_n(k)\) уже построен, ответ записывается просто как
$$S_n=\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k).$$
Последовательность \(L_n(k)\) не возрастает по \(k\): чем больше требуется повторений, тем длиннее лучшая допустимая подстрока стать не может. Поэтому после первого нуля все последующие значения тоже равны нулю.
Для \(i=0,1,\dots,9\) две исходные последовательности имеют вид
$$a_i=(0,1,1,0,1,0,0,1,1,0),$$
$$b_i=(0,1,0,1,1,0,1,0,1,1).$$
После побитового XOR получаем
$$C_{10}=0011001101.$$
Теперь разберем повторы. Вся строка встречается один раз, значит \(L_{10}(1)=10\). Подстрока \(00110\) встречается дважды: на позициях \(1\)–\(5\) и \(5\)–\(9\) при единичной индексации, поэтому \(L_{10}(2)=5\). Подстрока \(01\) встречается три раза, а подстроки длины \(3\), встречающейся трижды, уже нет, следовательно \(L_{10}(3)=2\). Отдельные символы \(0\) и \(1\) появляются по пять раз, отсюда \(L_{10}(4)=L_{10}(5)=1\). Для \(k\ge 6\) значение становится нулевым.
Итак,
$$L_{10}(k)=(10,5,2,1,1,0,\dots),$$
а сумма положительных членов равна
$$10+5+2+1+1=19.$$
Это совпадает с малыми контрольными значениями реализации, в частности с \(L_{10}(2)=5\) и \(L_{10}(3)=2\).
Реализации на C++, Python и Java генерируют символы строки \(C_n\) на лету и сразу добавляют их в суффиксный автомат, не создавая никаких квадратичных таблиц подстрок. Поскольку алфавит двоичный, у каждого состояния достаточно хранить две исходящие дуги, одну суффиксную ссылку, максимальную представляемую длину и счетчик вхождений.
После завершения построения состояния сортируются по максимальной длине при помощи counting sort и затем просматриваются от больших длин к меньшим, чтобы правильно протолкнуть счетчики по суффиксным ссылкам. Затем для каждого точного числа вхождений сохраняется наибольшая длина, достигнутая каким-либо состоянием с этим счетчиком. Один проход суффиксных максимумов превращает эти точные корзины в требуемые значения \(L_n(k)\). В конце положительные члены суммируются, а после первого нуля можно остановиться.
Пусть \(n\) — длина строки. Генерация битов и построение суффиксного автомата занимают линейное время, а число состояний автомата не превосходит \(2n-1\). Сортировка состояний по длине через counting sort работает за \(O(n)\), распространение счетчиков по суффиксным ссылкам — тоже за \(O(n)\), и завершающие проходы по массивам частот также линейны. Следовательно, общая сложность равна \(O(n)\) по времени и \(O(n)\) по памяти.
لـ \(0 \le i \lt n\) نعرّف
$$a_i=\operatorname{popcount}(i)\bmod 2,\qquad b_i=\left\lfloor\frac{i+1}{\varphi}\right\rfloor-\left\lfloor\frac{i}{\varphi}\right\rfloor,\qquad c_i=a_i\oplus b_i,$$
حيث \(\varphi=\frac{1+\sqrt{5}}{2}\). ومن ثم تتكون الكلمة الثنائية
$$C_n=c_0c_1\dots c_{n-1}.$$
ولكل \(k\ge 1\)، فإن \(L_n(k)\) هو أكبر طول لمقطع فرعي من \(C_n\) يظهر على الأقل \(k\) مرات، مع السماح بالتداخل بين الظهورات. المطلوب هو حساب
$$\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k)$$
عندما \(n=5{,}000{,}000\). وبما أن عدد المقاطع الفرعية الممكنة من رتبة تربيعية، فلا يمكن فحصها واحدًا واحدًا؛ لذلك يجب ضغط بنية التكرارات كلها في تمثيل خطي.
بعد تكوين الكلمة \(C_n\)، تتحول المسألة إلى سؤال عن عدد مرات ظهور كل مقطع فرعي مختلف داخل سلسلة ثنائية ثابتة واحدة. الأداة المناسبة هنا هي suffix automaton، لأنها تمثل جميع المقاطع الفرعية المختلفة في مساحة خطية، وتحتفظ في الوقت نفسه بما يكفي من البنية لاستخراج عدد مرات الظهور لكل فئة.
القيمة \(a_i\) هي زوجية عدد البتات التي تساوي \(1\) في التمثيل الثنائي للعدد \(i\)، أي إنها بت متتالية Thue-Morse عند الموضع \(i\). أما \(b_i\) فهو فرق Beatty. وبما أن
$$\frac{1}{\varphi}=\varphi-1\in(0,1),$$
فإن المتتالية
$$\left\lfloor\frac{i}{\varphi}\right\rfloor$$
لا يمكن أن تزيد عند الانتقال من \(i\) إلى \(i+1\) إلا بمقدار \(0\) أو \(1\). لذلك
$$b_i\in\{0,1\}.$$
ومن ثم تبقى \(c_i=a_i\oplus b_i\) قيمة ثنائية أيضًا، ويصبح دخل مسألة السلاسل هو الكلمة الثنائية \(C_n\) نفسها. توليد هذه الكلمة يتم في \(O(n)\) زمنًا.
يقوم suffix automaton بتجميع المقاطع الفرعية بحسب مجموعة مواضع النهاية الخاصة بها. كل حالة \(v\) تمثل فئة تكافؤ من المقاطع التي تنتهي في المواضع نفسها تمامًا داخل \(C_n\). لنرمز بـ \(M(v)\) إلى أكبر طول تمثله الحالة \(v\). وإذا كانت وصلة اللاحقة للحالة \(v\) تشير إلى الحالة \(u\)، فإن الأطوال التي تغطيها هذه الحالة هي
$$M(u)+1,\ M(u)+2,\ \dots,\ M(v).$$
وهذا يعني أن كل مقطع فرعي مختلف ينتمي إلى حالة واحدة بالضبط، وأن أطول عنصر داخل تلك الفئة طوله \(M(v)\). وبالنسبة إلى سلسلة طولها \(n\)، فإن عدد حالات suffix automaton لا يتجاوز \(2n-1\)، ولهذا يبقى التمثيل خطيًا في الحجم.
أثناء البناء المتدرج من اليسار إلى اليمين، فإن كل حالة جديدة غير مستنسخة تقابل لاحقة جديدة تنتهي عند الموضع الحالي، ولذلك تبدأ بعدّاد يساوي \(1\). أما الحالات المستنسخة فتبدأ من الصفر، لأنها لا تضيف ظهورًا جديدًا بحد ذاتها، بل تعيد تنظيم البنية الموجودة فقط.
بعد إدخال السلسلة كاملة، تُعالَج الحالات بترتيب تنازلي بحسب \(M(v)\). وعندما تدفع حالة \(v\) مجموعها إلى الحالة الأب عبر وصلة اللاحقة، تكون جميع الفئات الأطول قد جُمعت سابقًا، فيتحول هذا المجموع إلى حجم مجموعة مواضع النهاية الخاصة بالحالة. إذا رمزنا إلى هذا العدد النهائي بـ \(R(v)\)، فإن أي مقطع فرعي تمثله الحالة \(v\) يظهر في \(C_n\) بالضبط \(R(v)\) مرة.
هذا العد يشمل التكرارات المتداخلة تلقائيًا، لأن مواضع النهاية المختلفة تُحسب بشكل مستقل حتى لو كانت مقاطع الظهور نفسها تتشارك بعض الحروف.
ثبّت حالة \(v\). جميع المقاطع التي تمثلها هذه الحالة تظهر العدد نفسه من المرات، وهو \(R(v)\)، لكن أطوالها تتراوح داخل المجال المرتبط بالحالة. بالنسبة إلى \(L_n(k)\)، لا يهمنا من هذه الفئة إلا أطول مقطع، لأننا نبحث عن أكبر طول ممكن بين جميع المقاطع التي تحقق شرط عدد الظهورات. لذلك فإن الحالة \(v\) تساهم بالقيمة \(M(v)\) في الحاوية الخاصة بعدد الظهورات الدقيق \(R(v)\).
إذا كانت \(B(t)\) تمثل أكبر طول شوهد بين الحالات التي يظهر مقطعها بالضبط \(t\) مرات، فإن التحديث يكون
$$B(R(v))=\max\bigl(B(R(v)),M(v)\bigr).$$
لكن المطلوب في المسألة هو “على الأقل \(k\) مرات”، لا “بالضبط \(k\) مرات”. لهذا نأخذ قيمة عظمى لاحقة:
$$L_n(k)=\max_{t\ge k} B(t).$$
وتمريرة واحدة من اليمين إلى اليسار على مصفوفة العدادات تكفي لاستخراج جميع القيم \(L_n(1),L_n(2),\dots,L_n(n)\).
بعد معرفة جميع قيم \(L_n(k)\)، يصبح الجواب المطلوب
$$S_n=\sum_{\substack{k\ge 1\\L_n(k)>0}} L_n(k).$$
والمتتالية \(L_n(k)\) غير متزايدة بالنسبة إلى \(k\): فكلما طلبنا عدد تكرارات أكبر، لا يمكن أن يصبح أفضل مقطع أطول. ولهذا، ما إن تصل القيم إلى الصفر حتى تبقى جميع القيم اللاحقة صفرًا أيضًا.
عندما \(i=0,1,\dots,9\)، نحصل على المتتاليتين
$$a_i=(0,1,1,0,1,0,0,1,1,0),$$
$$b_i=(0,1,0,1,1,0,1,0,1,1).$$
وبأخذ XOR بتًا بت نحصل على
$$C_{10}=0011001101.$$
الآن نفحص التكرارات. السلسلة كلها تظهر مرة واحدة، إذن \(L_{10}(1)=10\). المقطع \(00110\) يظهر مرتين، في الموضعين \(1\) إلى \(5\) ثم \(5\) إلى \(9\) باستخدام ترقيم يبدأ من \(1\)، لذلك \(L_{10}(2)=5\). كما أن المقطع \(01\) يظهر ثلاث مرات، ولا يوجد أي مقطع بطول \(3\) يظهر ثلاث مرات، ومن ثم \(L_{10}(3)=2\). أما الرمزان المنفردان \(0\) و\(1\) فيظهر كل منهما خمس مرات، ولهذا \(L_{10}(4)=L_{10}(5)=1\). وبالنسبة إلى \(k\ge 6\) تصبح القيمة صفرًا.
إذن
$$L_{10}(k)=(10,5,2,1,1,0,\dots),$$
ومجموع الحدود الموجبة يساوي
$$10+5+2+1+1=19.$$
وهذا يطابق نقاط التحقق الصغيرة الموجودة في التنفيذ، وخصوصًا \(L_{10}(2)=5\) و\(L_{10}(3)=2\).
تنشئ تطبيقات C++ وPython وJava بتات \(C_n\) أثناء السير، ثم تضيف كل بت مباشرة إلى suffix automaton، من دون إنشاء أي جدول تربيعي للمقاطع الفرعية. وبما أن الأبجدية هي \(\{0,1\}\) فقط، فكل حالة تحتاج إلى انتقالين خارجيين لا أكثر، مع وصلة لاحقة، وطول أقصى ممثل، وعداد للظهورات.
بعد اكتمال بناء الآلة، يرتب التنفيذ الحالات بحسب الطول الأقصى باستخدام counting sort، ثم يعالجها من الأطول إلى الأقصر لكي تنتقل أعداد الظهور على طول وصلات اللاحقة بالترتيب الصحيح. بعد ذلك يسجل، لكل عدد ظهور دقيق، أكبر طول وصل إليه أي تمثيل في تلك الفئة. ثم يحول تمرير واحد للقيم العظمى اللاحقة هذه الحاويات الدقيقة إلى القيم المطلوبة \(L_n(k)\). وفي النهاية تُجمع الحدود الموجبة، ويمكن التوقف فور الوصول إلى أول صفر.
إذا كان \(n\) هو طول السلسلة، فإن توليد البتات وبناء suffix automaton يتمان في \(O(n)\) زمنًا، وعدد الحالات لا يتجاوز \(2n-1\). وفرز الحالات بحسب الطول باستخدام counting sort يكلف \(O(n)\)، وكذلك نشر أعداد الظهور عبر وصلات اللاحقة، كما أن المرورين النهائيين على مصفوفات العد يظلان خطيين أيضًا. لذلك يكون التعقيد الكلي \(O(n)\) زمنًا و\(O(n)\) ذاكرة.