Let
$$\mathcal{P}=\{\text{FREE},\text{FARE},\text{AREA},\text{REEF}\}.$$
We want the number \(F(n)\) of length-\(n\) words over the alphabet \(\{A,E,F,R\}\) in which every word in \(\mathcal{P}\) appears exactly once as a contiguous substring. For the actual problem one needs \(F(30)\).
A brute-force search would inspect \(4^n\) words, which is hopeless for \(n=30\). The difficulty is not just the size of the search space: the four target words overlap in several ways, so ordinary inclusion-exclusion becomes awkward. The implementations therefore convert the problem into a finite-state dynamic program that records both the current suffix information and how many times each target has already been completed.
The key observation is that only two pieces of information matter after reading a prefix: which suffixes can still grow into one of the target words, and how many times each target word has already been seen. That leads naturally to an Aho-Corasick automaton combined with dynamic programming.
Construct the trie of the four words in \(\mathcal{P}\), then add failure links in the standard Aho-Corasick way. After processing a prefix \(u\), the automaton state represents the longest suffix of \(u\) that is also a prefix of at least one word in \(\mathcal{P}\).
For every state \(s\) and next letter \(\sigma\in\{A,E,F,R\}\), there is a deterministic transition
$$\delta(s,\sigma).$$
Each state also carries an output vector
$$m(s)=\bigl(m_1(s),m_2(s),m_3(s),m_4(s)\bigr),$$
where \(m_i(s)\) is the number of times the \(i\)-th target word ends when we arrive at \(s\), after suffix outputs from failure links have been propagated. This is exactly what lets one transition detect newly completed matches, even when overlaps are involved.
For a processed prefix of length \(\ell\), define
$$D_\ell\bigl(s,c_1,c_2,c_3,c_4\bigr)$$
to be the number of prefixes of length \(\ell\) that end in automaton state \(s\) and have seen the four target words with capped counts \(c_i\in\{0,1,2\}\). Here
$$c_i=0 \text{ means “not seen yet,”}\qquad c_i=1 \text{ means “seen exactly once,”}$$
and
$$c_i=2 \text{ means “seen at least twice.”}$$
This cap is enough because any word with some \(c_i=2\) can never contribute to the final answer. We do not need to distinguish between two occurrences and three occurrences; both are already invalid.
The initial condition is
$$D_0(0,0,0,0,0)=1,$$
with every other state equal to \(0\).
Suppose a length-\(\ell\) prefix is counted by \(D_\ell(s,c_1,c_2,c_3,c_4)\), and we append one letter \(\sigma\). The automaton moves to
$$s'=\delta(s,\sigma).$$
The new capped counts are
$$c_i'=\min\bigl(2,\;c_i+m_i(s')\bigr)\qquad (1\le i\le 4).$$
If at least one \(c_i'=2\), this branch is discarded immediately. Otherwise we add
$$D_\ell(s,c_1,c_2,c_3,c_4)$$
to
$$D_{\ell+1}(s',c_1',c_2',c_3',c_4').$$
This recurrence is exact because appending one letter changes the future only through the new automaton state and the updated occurrence profile.
The goal is “exactly once” for every target word. Therefore every valid completed word must end with profile
$$\bigl(1,1,1,1\bigr).$$
If some component ever reaches \(2\), then one of the target words has already appeared at least twice, and no continuation can repair that. So pruning those branches is logically exact, not merely a heuristic.
This is what makes the state space small. Instead of storing arbitrary occurrence numbers, the dynamic program only needs \(3^4=81\) occurrence profiles for each automaton state.
After processing all \(n\) letters, we sum over all automaton states with the exact target profile:
$$\boxed{F(n)=\sum_s D_n\bigl(s,1,1,1,1\bigr).}$$
No extra correction term is required. The transition rule already enforced “at most once,” and the final profile enforces “at least once.” Together they give “exactly once.”
A concrete valid word is
$$\text{FREEFAREA}.$$
Its important length-4 substrings are
$$\text{FREE},\ \text{REEF},\ \text{FARE},\ \text{AREA},$$
each appearing exactly once. The occurrence profile evolves as follows:
$$\begin{aligned} \text{after FREE} &\longrightarrow (1,0,0,0),\\ \text{after FREEF} &\longrightarrow (1,0,0,1),\\ \text{after FREEFARE} &\longrightarrow (1,1,0,1),\\ \text{after FREEFAREA} &\longrightarrow (1,1,1,1). \end{aligned}$$
The implementations also check the checkpoint
$$F(9)=1,$$
so this length-9 construction is not merely valid; it is the unique valid word of that length.
The C++, Python, and Java implementations all follow the same plan. First they build the trie for the four target words and perform a breadth-first construction of failure links. During that process, each state receives the accumulated output information from its failure ancestor, so every transition already knows which target words have just ended.
Next, the implementation allocates two rolling dynamic-programming layers. Each automaton state is paired with one of the \(81\) capped occurrence profiles, so a whole layer is just a flat table indexed by “automaton state + profile.” The base layer contains one way to be at the root with all counts equal to \(0\).
For each of the \(30\) character positions, the current layer is scanned. From every nonzero entry, the implementation tries the four possible next letters, follows the precomputed automaton transition, updates the four capped counts, and discards the transition whenever some target word would be counted for a second time. Otherwise the number of ways is added to the destination entry in the next layer.
After the last position, the implementation sums all entries whose profile is exactly \((1,1,1,1)\). The C++ version also includes two small sanity checks, namely \(F(9)=1\) and \(F(15)=72863\), before producing the value for \(F(30)\).
Let \(S\) be the number of automaton states. Building the automaton and its failure links costs \(O(S\cdot 4)\), since the alphabet size is \(4\). The dynamic program performs
$$O\bigl(n\cdot S\cdot 3^4\cdot 4\bigr)$$
operations, because for each position it scans every state, every capped occurrence profile, and every next letter.
Using rolling layers keeps the memory usage at
$$O(S\cdot 3^4).$$
For this particular problem the automaton is tiny: the trie of the four length-4 words has only \(16\) states, so each DP layer has \(16\cdot 81=1296\) entries. That is why the exact count for \(n=30\) is easy to obtain once the state formulation is set up correctly.
Sei
$$\mathcal{P}=\{\text{FREE},\text{FARE},\text{AREA},\text{REEF}\}.$$
Gesucht ist die Anzahl \(F(n)\) der Wörter der Länge \(n\) über dem Alphabet \(\{A,E,F,R\}\), in denen jedes Wort aus \(\mathcal{P}\) genau einmal als zusammenhängender Teilstring vorkommt. Für die eigentliche Aufgabe wird \(F(30)\) benötigt.
Eine vollständige Enumeration würde \(4^n\) Wörter prüfen und ist für \(n=30\) völlig unpraktikabel. Erschwerend kommt hinzu, dass sich die vier Zielwörter überlappen können. Deshalb formuliert die Lösung das Problem als dynamische Programmierung auf einem endlichen Automaten, der zugleich das relevante Suffix und die bisherigen Auftretenszahlen speichert.
Nach dem Lesen eines Präfixes sind nur zwei Informationen wesentlich: welches Suffix noch als Präfix eines Zielwortes weitergeführt werden kann und wie oft jedes Zielwort bereits vollständig erkannt wurde. Genau das liefert die Kombination aus Aho-Corasick-Automat und DP.
Man konstruiert zunächst den Trie der vier Wörter aus \(\mathcal{P}\) und ergänzt dann die Failure-Links des Aho-Corasick-Verfahrens. Nach einem gelesenen Präfix \(u\) beschreibt der Automat den längsten Suffix von \(u\), der zugleich Präfix mindestens eines Zielwortes ist.
Für jeden Zustand \(s\) und jeden nächsten Buchstaben \(\sigma\in\{A,E,F,R\}\) gibt es einen deterministischen Übergang
$$\delta(s,\sigma).$$
Zusätzlich trägt jeder Zustand einen Ausgabvektor
$$m(s)=\bigl(m_1(s),m_2(s),m_3(s),m_4(s)\bigr),$$
wobei \(m_i(s)\) angibt, wie oft das \(i\)-te Zielwort beim Erreichen von \(s\) endet, nachdem die Ausgaben entlang der Failure-Links bereits eingerechnet wurden. Dadurch erkennt ein einzelner Schritt korrekt alle neu abgeschlossenen Treffer, auch bei Überlappungen.
Für ein Präfix der Länge \(\ell\) definieren wir
$$D_\ell\bigl(s,c_1,c_2,c_3,c_4\bigr)$$
als die Anzahl der Präfixe der Länge \(\ell\), die im Automatenzustand \(s\) enden und die vier Zielwörter mit gekappten Zählern \(c_i\in\{0,1,2\}\) gesehen haben. Dabei bedeutet
$$c_i=0:\ \text{noch nicht gesehen},\qquad c_i=1:\ \text{genau einmal gesehen},$$
und
$$c_i=2:\ \text{mindestens zweimal gesehen}.$$
Diese Kappung reicht vollständig aus, denn jeder Zustand mit irgendeinem \(c_i=2\) ist für die Endsumme bereits unbrauchbar. Ob ein Muster zweimal oder fünfmal vorkam, spielt dann keine Rolle mehr.
Die Anfangsbedingung lautet
$$D_0(0,0,0,0,0)=1,$$
alle anderen Werte sind anfangs \(0\).
Nehmen wir an, ein Präfix der Länge \(\ell\) wird von \(D_\ell(s,c_1,c_2,c_3,c_4)\) gezählt, und wir hängen einen Buchstaben \(\sigma\) an. Dann wechselt der Automat nach
$$s'=\delta(s,\sigma).$$
Die neuen gekappten Zähler sind
$$c_i'=\min\bigl(2,\;c_i+m_i(s')\bigr)\qquad (1\le i\le 4).$$
Falls irgendein \(c_i'=2\) ist, wird dieser Zweig sofort verworfen. Andernfalls addieren wir
$$D_\ell(s,c_1,c_2,c_3,c_4)$$
zu
$$D_{\ell+1}(s',c_1',c_2',c_3',c_4').$$
Diese Rekurrenz ist exakt, weil ein weiterer Buchstabe die Zukunft nur über den neuen Automatenzustand und das aktualisierte Auftretensprofil beeinflusst.
Gesucht sind Wörter, in denen jedes Zielwort genau einmal vorkommt. Deshalb muss jedes gültige Endwort mit dem Profil
$$\bigl(1,1,1,1\bigr)$$
enden. Erreicht eine Komponente unterwegs den Wert \(2\), dann ist bereits klar, dass ein Zielwort mindestens zweimal vorgekommen ist. Kein späteres Anhängen weiterer Buchstaben kann das wieder reparieren.
Gerade diese Beobachtung hält den Zustandsraum klein. Pro Automatenzustand benötigt die DP nur \(3^4=81\) Auftretensprofile.
Nach dem Einlesen aller \(n\) Buchstaben summieren wir über alle Automatenzustände mit dem exakten Zielprofil:
$$\boxed{F(n)=\sum_s D_n\bigl(s,1,1,1,1\bigr).}$$
Ein zusätzlicher Korrekturterm ist nicht nötig. Die Übergänge erzwingen bereits „höchstens einmal“, und das Endprofil erzwingt „mindestens einmal“. Zusammen ergibt das „genau einmal“.
Ein konkretes gültiges Wort ist
$$\text{FREEFAREA}.$$
Die relevanten Teilstrings der Länge \(4\) sind
$$\text{FREE},\ \text{REEF},\ \text{FARE},\ \text{AREA},$$
und jeder davon tritt genau einmal auf. Das Auftretensprofil entwickelt sich so:
$$\begin{aligned} \text{nach FREE} &\longrightarrow (1,0,0,0),\\ \text{nach FREEF} &\longrightarrow (1,0,0,1),\\ \text{nach FREEFARE} &\longrightarrow (1,1,0,1),\\ \text{nach FREEFAREA} &\longrightarrow (1,1,1,1). \end{aligned}$$
Die Implementierungen prüfen außerdem den Kontrollwert
$$F(9)=1,$$
daher ist dies nicht nur ein gültiges Beispiel, sondern sogar das einzige gültige Wort der Länge \(9\).
Die C++-, Python- und Java-Implementierungen folgen alle demselben Schema. Zuerst bauen sie den Trie der vier Zielwörter auf und berechnen per Breitensuche die Failure-Links. Dabei wird die Ausgabinformation des Failure-Vorgängers in jeden Zustand hineingefaltet, sodass jeder Übergang sofort weiß, welche Zielwörter gerade abgeschlossen wurden.
Anschließend verwendet die Implementierung zwei rollierende DP-Schichten. Jeder Automatenzustand wird mit einem der \(81\) gekappten Auftretensprofile kombiniert; eine ganze Schicht ist also einfach eine flache Tabelle über „Zustand + Profil“. In der Startschicht gibt es genau eine Möglichkeit: die leere Zeichenkette am Wurzelzustand mit vier Nullen.
Für jede der \(30\) Positionen wird die aktuelle Schicht durchlaufen. Von jedem nichtleeren Eintrag aus probiert die Implementierung die vier möglichen nächsten Buchstaben, folgt dem vorberechneten Automatenübergang, aktualisiert die vier gekappten Zähler und verwirft den Übergang sofort, falls damit irgendein Zielwort ein zweites Mal gezählt würde. Andernfalls wird die Anzahl der Wege in den Zielzustand der nächsten Schicht addiert.
Nach der letzten Position summiert die Implementierung alle Einträge mit Profil \((1,1,1,1)\). Die C++-Version enthält zusätzlich zwei kleine Plausibilitätsprüfungen, nämlich \(F(9)=1\) und \(F(15)=72863\), bevor der Wert für \(F(30)\) ausgegeben wird.
Sei \(S\) die Anzahl der Automatenzustände. Der Aufbau des Automaten samt Failure-Links kostet \(O(S\cdot 4)\), weil das Alphabet Größe \(4\) hat. Die dynamische Programmierung benötigt
$$O\bigl(n\cdot S\cdot 3^4\cdot 4\bigr)$$
Operationen, da für jede Position alle Zustände, alle gekappten Profile und alle vier nächsten Buchstaben betrachtet werden.
Mit zwei rollierenden Schichten bleibt der Speicherverbrauch bei
$$O(S\cdot 3^4).$$
In dieser konkreten Aufgabe ist der Automat sehr klein: Der Trie der vier Wörter der Länge \(4\) hat nur \(16\) Zustände. Eine DP-Schicht enthält also lediglich \(16\cdot 81=1296\) Einträge. Genau deshalb ist die exakte Berechnung für \(n=30\) problemlos, sobald der Zustandsraum richtig modelliert ist.
Şunu tanımlayalım:
$$\mathcal{P}=\{\text{FREE},\text{FARE},\text{AREA},\text{REEF}\}.$$
Aradığımız \(F(n)\) değeri, \(\{A,E,F,R\}\) alfabesi üzerinde uzunluğu \(n\) olan ve \(\mathcal{P}\) kümesindeki her kelimeyi bitişik alt dizi olarak tam bir kez içeren dizgilerin sayısıdır. Sorunun gerçek hedefi \(F(30)\)'dur.
Doğrudan kuvvet denemesi \(4^n\) olasılığı taramak zorunda kalır ve \(n=30\) için uygulanamaz. Üstelik dört hedef kelime birbirleriyle örtüşebildiği için sıradan dahil et-çıkar yaklaşımı da kolay değildir. Bu yüzden çözüm, problemi sonlu durumlu bir otomaton üzerinde çalışan bir dinamik programlama problemine dönüştürür.
Bir önek okunduktan sonra aslında sadece iki bilgi önemlidir: Sonunda kalan hangi ek parça hâlâ hedef kelimelerden birinin öneki olabilir ve dört hedef kelimenin her biri şu ana kadar kaç kez tamamlanmıştır? Aho-Corasick otomatonu ile DP'nin birlikte kullanılması tam olarak bu iki bilgiyi taşır.
Önce \(\mathcal{P}\) içindeki dört kelimenin trie yapısı kurulur, ardından Aho-Corasick yöntemindeki failure bağlantıları eklenir. İşlenen bir \(u\) önekinden sonra otomaton durumu, \(u\)'nun aynı zamanda en az bir hedef kelimenin öneki olan en uzun soneki temsil eder.
Her durum \(s\) ve her sonraki harf \(\sigma\in\{A,E,F,R\}\) için belirli bir geçiş vardır:
$$\delta(s,\sigma).$$
Her durum ayrıca bir çıktı vektörü taşır:
$$m(s)=\bigl(m_1(s),m_2(s),m_3(s),m_4(s)\bigr).$$
Burada \(m_i(s)\), failure bağlantılarından gelen ek bilgiler de toplandıktan sonra, \(s\) durumuna ulaşıldığında \(i\). hedef kelimenin kaç kez bittiğini gösterir. Bu sayede örtüşmeler olsa bile tek bir geçişte yeni tamamlanan tüm eşleşmeler doğru biçimde yakalanır.
Uzunluğu \(\ell\) olan bir önek için
$$D_\ell\bigl(s,c_1,c_2,c_3,c_4\bigr)$$
ifadesini, otomaton durumu \(s\)'de biten ve dört hedef kelimeyi kırpılmış sayılarla \(c_i\in\{0,1,2\}\) kez görmüş öneklerin sayısı olarak tanımlayalım. Burada
$$c_i=0 \text{ “henüz görülmedi”,}\qquad c_i=1 \text{ “tam bir kez görüldü”}$$
ve
$$c_i=2 \text{ “en az iki kez görüldü”}$$
anlamına gelir. Bu kırpma yeterlidir; çünkü herhangi bir bileşeni \(2\) olan bir yol artık son cevapta yer alamaz. İki kez görmek ile daha fazla kez görmek arasında ek bir ayrım yapmaya gerek yoktur.
Başlangıç durumu
$$D_0(0,0,0,0,0)=1$$
şeklindedir; diğer tüm durumlar başlangıçta \(0\)'dır.
Diyelim ki uzunluğu \(\ell\) olan bir önek, \(D_\ell(s,c_1,c_2,c_3,c_4)\) tarafından sayılıyor ve sonuna bir \(\sigma\) harfi ekliyoruz. Otomaton
$$s'=\delta(s,\sigma)$$
durumuna gider. Yeni kırpılmış sayaçlar
$$c_i'=\min\bigl(2,\;c_i+m_i(s')\bigr)\qquad (1\le i\le 4)$$
olur. Eğer herhangi bir \(c_i'=2\) ise bu dal anında elenir. Aksi halde
$$D_\ell(s,c_1,c_2,c_3,c_4)$$
değeri
$$D_{\ell+1}(s',c_1',c_2',c_3',c_4')$$
üzerine eklenir. Bu bağıntı tamdır; çünkü bir harf eklendikten sonra geleceği belirleyen tek şey yeni otomaton durumu ile güncellenmiş görülme profilidir.
Hedefimiz her kelimenin tam bir kez görünmesidir. O halde geçerli bir tamamlanmış kelimenin son profili mutlaka
$$\bigl(1,1,1,1\bigr)$$
olmalıdır. Eğer herhangi bir bileşen bir ara \(2\)'ye ulaşırsa, artık o hedef kelime en az iki kez geçmiştir ve sonradan eklenecek harfler bunu düzeltemez.
Bu gözlem durum uzayını küçük tutar. Her otomaton durumu için yalnızca \(3^4=81\) farklı görülme profili gerekir.
Tüm \(n\) harf işlendiğinde, tam hedef profiline sahip tüm otomaton durumları toplanır:
$$\boxed{F(n)=\sum_s D_n\bigl(s,1,1,1,1\bigr).}$$
Ek bir düzeltme terimi gerekmez. Geçişler zaten “en fazla bir kez” koşulunu çevrim içi biçimde uygular; son profil de “en az bir kez” koşulunu uygular. Birlikte “tam bir kez” elde edilir.
Geçerli bir örnek dizgi şudur:
$$\text{FREEFAREA}.$$
Uzunluğu \(4\) olan önemli alt dizgiler
$$\text{FREE},\ \text{REEF},\ \text{FARE},\ \text{AREA}$$
olup her biri tam bir kez görünür. Görülme profili şu şekilde ilerler:
$$\begin{aligned} \text{FREE sonrası} &\longrightarrow (1,0,0,0),\\ \text{FREEF sonrası} &\longrightarrow (1,0,0,1),\\ \text{FREEFARE sonrası} &\longrightarrow (1,1,0,1),\\ \text{FREEFAREA sonrası} &\longrightarrow (1,1,1,1). \end{aligned}$$
Uygulamalar ayrıca
$$F(9)=1$$
kontrolünü de yapar; dolayısıyla bu yalnızca geçerli bir örnek değil, uzunluğu \(9\) olan tek geçerli dizgidir.
C++, Python ve Java uygulamaları aynı planı izler. Önce dört hedef kelimenin trie yapısı kurulup breadth-first sırayla failure bağlantıları hesaplanır. Bu aşamada her durum, failure atası üzerinden gelen çıktı bilgisini de içine alır; böylece bir geçiş yapıldığında hangi hedef kelimelerin o adımda tamamlandığı hazır olarak elde edilir.
Daha sonra uygulama iki dönen DP katmanı kullanır. Her otomaton durumu, \(81\) adet kırpılmış görülme profilinden biriyle eşleştirilir; bu yüzden tek bir katman “durum + profil” indeksli düz bir tablo gibi davranır. Başlangıçta kök durumda ve dört sayaç da sıfırken tek bir yol vardır.
\(30\) konumun her birinde mevcut katman taranır. Sıfır olmayan her giriş için dört olası sonraki harf denenir, önceden hesaplanmış otomaton geçişi izlenir, dört sayaç kırpılmış biçimde güncellenir ve eğer bir hedef kelime ikinci kez sayılacaksa bu geçiş hemen atılır. Aksi halde yol sayısı bir sonraki katmandaki uygun hücreye eklenir.
Son konumdan sonra profilin tam olarak \((1,1,1,1)\) olduğu tüm girişler toplanır. C++ uygulaması ayrıca \(F(9)=1\) ve \(F(15)=72863\) değerlerini küçük doğrulama testleri olarak kontrol eder; ardından \(F(30)\) sonucunu üretir.
\(S\) otomaton durum sayısı olsun. Otomatonu ve failure bağlantılarını kurmak, alfabe boyutu \(4\) olduğu için \(O(S\cdot 4)\) maliyetlidir. Dinamik programlama kısmı ise
$$O\bigl(n\cdot S\cdot 3^4\cdot 4\bigr)$$
işlem yapar; çünkü her konumda tüm durumlar, tüm kırpılmış profiller ve dört sonraki harf gözden geçirilir.
İki dönen katman kullanıldığı için bellek gereksinimi
$$O(S\cdot 3^4)$$
düzeyindedir. Bu problemde otomaton çok küçüktür: Dört adet uzunluğu \(4\) olan kelimenin trie'ı yalnızca \(16\) durum içerir. Dolayısıyla tek bir DP katmanında sadece \(16\cdot 81=1296\) hücre vardır. Bu yüzden doğru durum tanımı kurulduktan sonra \(n=30\) için tam sayımı yapmak oldukça rahattır.
Definimos
$$\mathcal{P}=\{\text{FREE},\text{FARE},\text{AREA},\text{REEF}\}.$$
Buscamos \(F(n)\), el número de palabras de longitud \(n\) sobre el alfabeto \(\{A,E,F,R\}\) en las que cada palabra de \(\mathcal{P}\) aparece exactamente una vez como subcadena contigua. En el problema real se necesita \(F(30)\).
Una búsqueda exhaustiva tendría que revisar \(4^n\) palabras, algo imposible para \(n=30\). Además, las cuatro palabras objetivo pueden solaparse, así que una inclusión-exclusión directa resulta incómoda. Por eso la solución transforma el problema en una programación dinámica sobre un autómata finito que recuerda tanto el sufijo relevante como el número de apariciones ya completadas de cada patrón.
Después de leer un prefijo, solo importan dos cosas: qué sufijo todavía puede prolongarse hasta convertirse en prefijo de una palabra objetivo y cuántas veces ya ha aparecido cada objetivo. Esa es exactamente la información que captura la combinación de autómata Aho-Corasick y programación dinámica.
Primero se construye el trie de las cuatro palabras de \(\mathcal{P}\), y luego se añaden los enlaces de fallo del algoritmo de Aho-Corasick. Tras procesar un prefijo \(u\), el estado del autómata representa el sufijo más largo de \(u\) que también es prefijo de al menos una palabra objetivo.
Para cada estado \(s\) y cada letra siguiente \(\sigma\in\{A,E,F,R\}\), existe una transición determinista
$$\delta(s,\sigma).$$
Cada estado también lleva un vector de salida
$$m(s)=\bigl(m_1(s),m_2(s),m_3(s),m_4(s)\bigr),$$
donde \(m_i(s)\) indica cuántas veces termina la \(i\)-ésima palabra objetivo al llegar a \(s\), después de propagar las salidas que vienen por los enlaces de fallo. Eso permite detectar todos los nuevos aciertos de un solo paso, incluso cuando hay solapamientos.
Para un prefijo de longitud \(\ell\), definimos
$$D_\ell\bigl(s,c_1,c_2,c_3,c_4\bigr)$$
como el número de prefijos de longitud \(\ell\) que terminan en el estado \(s\) y han visto las cuatro palabras objetivo con contadores truncados \(c_i\in\{0,1,2\}\). Aquí
$$c_i=0 \text{ significa “todavía no apareció”,}\qquad c_i=1 \text{ significa “apareció exactamente una vez”,}$$
y
$$c_i=2 \text{ significa “apareció al menos dos veces”.}$$
Ese truncamiento es suficiente, porque cualquier palabra con algún \(c_i=2\) ya no puede contribuir a la respuesta final. No hace falta distinguir entre dos apariciones y tres o más.
La condición inicial es
$$D_0(0,0,0,0,0)=1,$$
mientras que todos los demás estados comienzan en \(0\).
Supongamos que un prefijo de longitud \(\ell\) está contado por \(D_\ell(s,c_1,c_2,c_3,c_4)\), y añadimos una letra \(\sigma\). El autómata pasa a
$$s'=\delta(s,\sigma).$$
Los nuevos contadores truncados son
$$c_i'=\min\bigl(2,\;c_i+m_i(s')\bigr)\qquad (1\le i\le 4).$$
Si algún \(c_i'=2\), esa rama se descarta inmediatamente. En caso contrario, sumamos
$$D_\ell(s,c_1,c_2,c_3,c_4)$$
a
$$D_{\ell+1}(s',c_1',c_2',c_3',c_4').$$
La recurrencia es exacta porque, tras añadir una letra, el futuro solo depende del nuevo estado del autómata y del perfil actualizado de apariciones.
El objetivo es que cada palabra objetivo aparezca exactamente una vez. Por lo tanto, toda palabra válida completa debe terminar con el perfil
$$\bigl(1,1,1,1\bigr).$$
Si algún componente llega a \(2\), entonces una de las palabras objetivo ya apareció al menos dos veces, y ninguna continuación puede arreglar eso. Así que la poda es exacta, no heurística.
Esta observación reduce mucho el espacio de estados: para cada estado del autómata solo hacen falta \(3^4=81\) perfiles de aparición.
Después de procesar las \(n\) letras, sumamos todos los estados del autómata cuyo perfil sea exactamente el objetivo:
$$\boxed{F(n)=\sum_s D_n\bigl(s,1,1,1,1\bigr).}$$
No hace falta ningún término de corrección adicional. La transición ya impone “como mucho una vez”, y el perfil final impone “al menos una vez”. Juntas, ambas condiciones equivalen a “exactamente una vez”.
Una palabra válida concreta es
$$\text{FREEFAREA}.$$
Sus subcadenas importantes de longitud \(4\) son
$$\text{FREE},\ \text{REEF},\ \text{FARE},\ \text{AREA},$$
cada una exactamente una vez. El perfil de apariciones evoluciona así:
$$\begin{aligned} \text{después de FREE} &\longrightarrow (1,0,0,0),\\ \text{después de FREEF} &\longrightarrow (1,0,0,1),\\ \text{después de FREEFARE} &\longrightarrow (1,1,0,1),\\ \text{después de FREEFAREA} &\longrightarrow (1,1,1,1). \end{aligned}$$
Además, las implementaciones verifican el valor de control
$$F(9)=1,$$
de modo que esta construcción no solo es válida, sino que es la única palabra válida de longitud \(9\).
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Primero construyen el trie de las cuatro palabras objetivo y calculan los enlaces de fallo mediante un recorrido en anchura. Durante ese proceso, cada estado acumula también la información de salida de su ancestro por fallo, de modo que cada transición ya sabe qué palabras objetivo acaban de completarse.
Después, la implementación reserva dos capas rotativas de programación dinámica. Cada estado del autómata se combina con uno de los \(81\) perfiles de apariciones truncados, así que cada capa es una tabla plana indexada por “estado del autómata + perfil”. La capa inicial contiene una única forma de estar en la raíz con los cuatro contadores iguales a \(0\).
Para cada una de las \(30\) posiciones, la capa actual se recorre por completo. Desde cada entrada no nula, la implementación prueba las cuatro letras posibles, sigue la transición ya precomputada del autómata, actualiza los cuatro contadores truncados y descarta la transición si alguna palabra objetivo sería contada por segunda vez. En caso contrario, el número de formas se suma a la celda correspondiente de la siguiente capa.
Al final, la implementación suma todas las entradas cuyo perfil es exactamente \((1,1,1,1)\). La versión en C++ también incluye dos comprobaciones pequeñas, \(F(9)=1\) y \(F(15)=72863\), antes de producir el valor de \(F(30)\).
Sea \(S\) el número de estados del autómata. Construir el autómata y sus enlaces de fallo cuesta \(O(S\cdot 4)\), ya que el alfabeto tiene tamaño \(4\). La programación dinámica realiza
$$O\bigl(n\cdot S\cdot 3^4\cdot 4\bigr)$$
operaciones, porque para cada posición examina todos los estados, todos los perfiles truncados y las cuatro letras posibles.
El uso de dos capas rotativas deja la memoria en
$$O(S\cdot 3^4).$$
En este problema concreto el autómata es muy pequeño: el trie de las cuatro palabras de longitud \(4\) tiene solo \(16\) estados. Por tanto, cada capa de DP contiene únicamente \(16\cdot 81=1296\) celdas. Esa es la razón de que el conteo exacto para \(n=30\) sea perfectamente manejable una vez formulado correctamente el estado.
定义
$$\mathcal{P}=\{\text{FREE},\text{FARE},\text{AREA},\text{REEF}\}.$$
我们要求的是 \(F(n)\)：在字母表 \(\{A,E,F,R\}\) 上，长度为 \(n\) 的字符串中，\(\mathcal{P}\) 里的四个单词都恰好出现一次的字符串个数。题目真正需要的是 \(F(30)\)。
如果直接暴力枚举，就要检查 \(4^n\) 个字符串，对 \(n=30\) 显然不可行。更麻烦的是，这四个目标单词之间存在重叠，例如一个位置既可能结束一个模式，又可能为另一个模式提供前缀结构。因此，解法不是做朴素枚举，也不是做繁琐的容斥，而是把问题改写成“自动机状态 + 出现次数轮廓”的动态规划。
当我们从左到右读入一个前缀时，真正影响未来的只有两类信息：第一，当前后缀中有哪些部分仍可能继续扩展成目标单词的前缀；第二，四个目标单词目前各自已经完整出现了几次。Aho-Corasick 自动机负责保存第一类信息，动态规划负责保存第二类信息。
先把 \(\mathcal{P}\) 中的四个单词建立成一棵 trie，然后按 Aho-Corasick 的标准方法补上 failure 链。处理完某个前缀 \(u\) 之后，自动机所在的状态表示：\(u\) 的最长后缀中，哪一段同时也是至少一个目标单词的前缀。
对每个状态 \(s\) 和每个下一字符 \(\sigma\in\{A,E,F,R\}\)，都有确定的转移
$$\delta(s,\sigma).$$
此外，每个状态还带有一个输出向量
$$m(s)=\bigl(m_1(s),m_2(s),m_3(s),m_4(s)\bigr),$$
其中 \(m_i(s)\) 表示到达状态 \(s\) 时，第 \(i\) 个目标单词在当前位置结束了多少次；这里已经把 failure 链上继承来的输出一并累计进去。这样一来，只要完成一次状态转移，就能立刻知道这一步新产生了哪些完整匹配，即使这些匹配来自重叠结构也不会漏掉。
对长度为 \(\ell\) 的前缀，定义
$$D_\ell\bigl(s,c_1,c_2,c_3,c_4\bigr)$$
表示满足以下条件的前缀数量：它的长度是 \(\ell\)，自动机停在状态 \(s\)，并且四个目标单词的出现次数被压缩记录为 \(c_i\in\{0,1,2\}\)。这里
$$c_i=0 \text{ 表示“还没有出现”，}\qquad c_i=1 \text{ 表示“恰好出现一次”，}$$
而
$$c_i=2 \text{ 表示“已经出现至少两次”。}$$
把计数截断到 \(2\) 就足够了，因为一旦某个目标单词已经出现两次，那么这条路径无论后面怎么延长，都不可能再成为合法答案。换句话说，我们根本不需要区分“出现两次”和“出现三次以上”。
初始条件是
$$D_0(0,0,0,0,0)=1,$$
其余所有状态一开始都为 \(0\)。
假设某个长度为 \(\ell\) 的前缀被 \(D_\ell(s,c_1,c_2,c_3,c_4)\) 计数，现在再接一个字符 \(\sigma\)。自动机会转移到
$$s'=\delta(s,\sigma).$$
新的截断计数为
$$c_i'=\min\bigl(2,\;c_i+m_i(s')\bigr)\qquad (1\le i\le 4).$$
如果某个 \(c_i'\) 变成了 \(2\)，说明对应目标单词已经至少出现两次，这条转移立刻剪枝。否则，就把
$$D_\ell(s,c_1,c_2,c_3,c_4)$$
加到
$$D_{\ell+1}(s',c_1',c_2',c_3',c_4').$$
这个递推是严格正确的，因为在追加一个字符之后，未来的所有可能性都只取决于新的自动机状态以及新的出现次数轮廓。
题目要求每个目标单词都“恰好一次”，因此任何合法的完整字符串在结束时都必须具有轮廓
$$\bigl(1,1,1,1\bigr).$$
如果在中途某个分量已经达到 \(2\)，那就说明某个目标单词至少出现了两次，而后续再加字符不可能把这个事实“修复”回去。所以这里的剪枝不是近似手段，而是逻辑上完全等价的删除无效状态。
这一步也是状态空间能够保持很小的关键。对每个自动机状态，只需要考虑 \(3^4=81\) 种出现次数轮廓。
处理完全部 \(n\) 个字符之后，对所有自动机状态求和，只保留目标轮廓 \((1,1,1,1)\)：
$$\boxed{F(n)=\sum_s D_n\bigl(s,1,1,1,1\bigr).}$$
这里不再需要额外的容斥修正。因为转移过程已经实时保证了“每个模式至多出现一次”，而最终轮廓又保证了“每个模式至少出现一次”，两者合起来正好就是“每个模式恰好出现一次”。
一个具体合法的长度 \(9\) 字符串是
$$\text{FREEFAREA}.$$
它的重要长度为 \(4\) 的子串正好是
$$\text{FREE},\ \text{REEF},\ \text{FARE},\ \text{AREA},$$
并且每个只出现一次。对应的出现次数轮廓依次变为
$$\begin{aligned} \text{读到 FREE 之后} &\longrightarrow (1,0,0,0),\\ \text{读到 FREEF 之后} &\longrightarrow (1,0,0,1),\\ \text{读到 FREEFARE 之后} &\longrightarrow (1,1,0,1),\\ \text{读到 FREEFAREA 之后} &\longrightarrow (1,1,1,1). \end{aligned}$$
实现里还检查了一个对照值：
$$F(9)=1.$$
因此这个例子不仅是一个合法构造，而且事实上是长度 \(9\) 时唯一的合法字符串。
C++、Python 和 Java 三个实现遵循完全相同的流程。第一步是建立四个目标单词的 trie，并用广度优先搜索构造 failure 链。在这个过程中，每个状态都会把 failure 祖先的输出信息累加进来，因此以后每做一次转移，就能立即知道这一步新结束了哪些目标单词。
第二步是分配两个滚动的动态规划层。每个自动机状态与 \(81\) 种截断后的出现次数轮廓之一配对，所以一整层本质上就是一张按“自动机状态 + 轮廓”索引的一维表。初始层里只有一个非零位置，也就是空字符串对应的根状态和四个零计数。
接下来对 \(30\) 个字符位置逐层推进。对于当前层里的每个非零条目，实现都会尝试四个可能的下一个字符，走预先算好的自动机转移，更新四个截断计数；如果某个目标单词因此会被第二次计入，则这一分支直接丢弃。否则，就把当前条目的方案数加到下一层的对应位置。
最后，在长度达到 \(30\) 之后，实现把所有轮廓恰好等于 \((1,1,1,1)\) 的条目相加。C++ 实现还额外包含两个小型校验，即 \(F(9)=1\) 和 \(F(15)=72863\)，然后才输出 \(F(30)\) 的值。
设自动机状态数为 \(S\)。建立自动机和 failure 链的代价是 \(O(S\cdot 4)\)，因为字母表大小就是 \(4\)。动态规划部分执行的操作数为
$$O\bigl(n\cdot S\cdot 3^4\cdot 4\bigr),$$
因为每一层都要遍历所有自动机状态、所有截断轮廓以及四种下一字符。
采用滚动数组以后，空间复杂度保持在
$$O(S\cdot 3^4).$$
对本题来说，这个常数非常小。四个长度为 \(4\) 的单词构成的 trie 只有 \(16\) 个状态，因此一层 DP 只有 \(16\cdot 81=1296\) 个单元。正因如此，只要状态设计正确，\(n=30\) 的精确计数计算起来就非常轻松。
Обозначим
$$\mathcal{P}=\{\text{FREE},\text{FARE},\text{AREA},\text{REEF}\}.$$
Нужно найти \(F(n)\): число слов длины \(n\) над алфавитом \(\{A,E,F,R\}\), в которых каждое слово из \(\mathcal{P}\) встречается ровно один раз как непрерывная подстрока. В самой задаче требуется значение \(F(30)\).
Полный перебор требует рассмотреть \(4^n\) слов и при \(n=30\) невозможен. Кроме того, четыре целевых слова могут сильно перекрываться, поэтому прямое включение-исключение получается громоздким. Именно поэтому решение переписывает задачу как динамику по конечному автомату, который хранит и информацию о значимом суффиксе, и уже набранные числа появлений каждого шаблона.
После чтения некоторого префикса для продолжения важны только две вещи: какой суффикс все еще может быть префиксом одного из целевых слов и сколько раз каждое целевое слово уже полностью встретилось. Эти две части информации естественно задаются автоматом Ахо-Корасик и динамическим программированием.
Сначала строится trie по четырем словам из \(\mathcal{P}\), затем стандартным образом добавляются failure-ссылки автомата Ахо-Корасик. После обработки префикса \(u\) текущее состояние автомата задает самый длинный суффикс строки \(u\), который одновременно является префиксом хотя бы одного целевого слова.
Для каждого состояния \(s\) и следующей буквы \(\sigma\in\{A,E,F,R\}\) существует детерминированный переход
$$\delta(s,\sigma).$$
Каждое состояние также имеет вектор выходов
$$m(s)=\bigl(m_1(s),m_2(s),m_3(s),m_4(s)\bigr),$$
где \(m_i(s)\) означает, сколько раз \(i\)-е целевое слово заканчивается при приходе в состояние \(s\) после того, как по failure-ссылкам уже накоплена вся суффиксная выходная информация. Благодаря этому один переход сразу обнаруживает все новые завершенные совпадения, в том числе возникающие из-за перекрытий.
Для префикса длины \(\ell\) введем величину
$$D_\ell\bigl(s,c_1,c_2,c_3,c_4\bigr),$$
которая обозначает число префиксов длины \(\ell\), заканчивающихся в состоянии \(s\) и имеющих усеченные счетчики \(c_i\in\{0,1,2\}\) для четырех целевых слов.
Здесь \(c_i=0\) означает, что соответствующее слово еще не встретилось, а \(c_i=1\) означает, что оно встретилось ровно один раз.
Значение \(c_i=2\) означает, что слово встретилось не менее двух раз.
Такого усечения достаточно, потому что любой путь с каким-либо \(c_i=2\) уже не может войти в окончательный ответ. Различать «два раза» и «три раза» больше не требуется.
Начальное условие имеет вид
$$D_0(0,0,0,0,0)=1,$$
а все остальные состояния изначально равны нулю.
Пусть некоторый префикс длины \(\ell\) учитывается в \(D_\ell(s,c_1,c_2,c_3,c_4)\), и мы дописываем одну букву \(\sigma\). Тогда автомат переходит в
$$s'=\delta(s,\sigma).$$
Новые усеченные счетчики равны
$$c_i'=\min\bigl(2,\;c_i+m_i(s')\bigr)\qquad (1\le i\le 4).$$
Если какой-то \(c_i'=2\), такая ветвь немедленно отбрасывается. Иначе значение
$$D_\ell(s,c_1,c_2,c_3,c_4)$$
добавляется в
$$D_{\ell+1}(s',c_1',c_2',c_3',c_4').$$
Эта рекурсия точна: после добавления одной буквы дальнейшее поведение зависит только от нового состояния автомата и обновленного профиля вхождений.
Цель задачи состоит в том, чтобы каждое целевое слово встретилось ровно один раз. Следовательно, всякая допустимая полная строка должна завершаться профилем
$$\bigl(1,1,1,1\bigr).$$
Если на каком-то этапе один из компонентов уже стал равен \(2\), то соответствующее слово встретилось как минимум дважды, и никакое продолжение не сможет это исправить. Поэтому такое отсечение не является эвристикой; оно логически эквивалентно удалению заведомо бесперспективных состояний.
Именно это делает пространство состояний маленьким: на каждое состояние автомата приходится всего \(3^4=81\) возможный профиль вхождений.
После обработки всех \(n\) букв нужно просуммировать все состояния автомата с точным целевым профилем:
$$\boxed{F(n)=\sum_s D_n\bigl(s,1,1,1,1\bigr).}$$
Никакой дополнительной поправки не требуется. Переходы уже обеспечивают условие «не более одного раза», а конечный профиль гарантирует условие «не менее одного раза». Вместе они дают «ровно один раз».
Конкретное допустимое слово имеет вид
$$\text{FREEFAREA}.$$
Его важные подстроки длины \(4\) таковы:
$$\text{FREE},\ \text{REEF},\ \text{FARE},\ \text{AREA},$$
и каждая встречается ровно один раз. Профиль вхождений меняется следующим образом:
$$\begin{aligned} \text{после FREE} &\longrightarrow (1,0,0,0),\\ \text{после FREEF} &\longrightarrow (1,0,0,1),\\ \text{после FREEFARE} &\longrightarrow (1,1,0,1),\\ \text{после FREEFAREA} &\longrightarrow (1,1,1,1). \end{aligned}$$
В реализациях также проверяется контрольное значение
$$F(9)=1,$$
поэтому это не просто допустимый пример, а единственное допустимое слово длины \(9\).
Реализации на C++, Python и Java устроены одинаково. Сначала строится trie по четырем целевым словам, затем обходом в ширину вычисляются failure-ссылки. По ходу этого процесса каждая вершина получает накопленную выходную информацию своего failure-предка, так что любой переход уже знает, какие целевые слова только что завершились.
После этого выделяются два чередующихся слоя динамики. Каждое состояние автомата сочетается с одним из \(81\) усеченных профилей вхождений, поэтому весь слой представляет собой плоскую таблицу по индексу «состояние автомата + профиль». В начальном слое есть ровно один ненулевой элемент: корень и четыре нуля.
Далее выполняются \(30\) шагов по длине строки. Для каждого ненулевого элемента текущего слоя реализация пробует все четыре возможные буквы, делает заранее подготовленный переход автомата, обновляет четыре усеченных счетчика и немедленно отбрасывает переход, если какое-либо целевое слово оказалось бы посчитано второй раз. Иначе число способов прибавляется в соответствующую ячейку следующего слоя.
После последнего шага суммируются все элементы с профилем \((1,1,1,1)\). В реализации на C++ есть также две небольшие проверки корректности: \(F(9)=1\) и \(F(15)=72863\), после чего выводится значение \(F(30)\).
Пусть \(S\) обозначает число состояний автомата. Построение автомата и failure-ссылок стоит \(O(S\cdot 4)\), поскольку размер алфавита равен \(4\). Динамическая программа выполняет
$$O\bigl(n\cdot S\cdot 3^4\cdot 4\bigr)$$
операций, потому что на каждом шаге по длине она перебирает все состояния, все усеченные профили и все четыре возможные следующие буквы.
Использование двух чередующихся слоев оставляет память на уровне
$$O(S\cdot 3^4).$$
Для данной задачи автомат очень мал: trie по четырем словам длины \(4\) содержит всего \(16\) состояний. Значит, один слой динамики имеет лишь \(16\cdot 81=1296\) ячеек. Именно поэтому точный ответ для \(n=30\) получается быстро, как только правильно выбрано пространство состояний.
لنعرّف
$$\mathcal{P}=\{\text{FREE},\text{FARE},\text{AREA},\text{REEF}\}.$$
المطلوب هو حساب \(F(n)\): عدد الكلمات ذات الطول \(n\) على الأبجدية \(\{A,E,F,R\}\) بحيث تظهر كل كلمة من عناصر \(\mathcal{P}\) مرة واحدة بالضبط كسلسلة فرعية متجاورة. وفي المسألة الأصلية نحتاج إلى \(F(30)\).
الفحص الشامل يحتاج إلى اختبار \(4^n\) كلمة، وهذا غير عملي إطلاقًا عندما يكون \(n=30\). كما أن الكلمات الأربع المستهدفة تتداخل فيما بينها بطرق مختلفة، لذلك فإن تطبيق مبدأ الشمول والاستبعاد مباشرة يصبح مزعجًا. لهذا السبب تتحول المسألة إلى برمجة ديناميكية فوق أوتوماتون منتهٍ يحتفظ بمعلومتين فقط: ما السلسلة اللاحقة المهمة حاليًا، وكم مرة اكتمل كل نمط حتى هذه اللحظة.
بعد قراءة أي بادئة من الكلمة، لا يبقى مهمًا إلا شيئان: أي لاحقة ما زالت قابلة لأن تمتد إلى بادئة أحد الأنماط المستهدفة، وكم مرة ظهر كل نمط كاملًا حتى الآن. أوتوماتون Aho-Corasick يلتقط المعلومة الأولى، والبرمجة الديناميكية تلتقط المعلومة الثانية.
نبدأ ببناء trie للكلمات الأربع في \(\mathcal{P}\)، ثم نضيف روابط الفشل وفق خوارزمية Aho-Corasick المعتادة. بعد معالجة بادئة \(u\)، تمثل حالة الأوتوماتون أطول لاحقة في \(u\) تكون أيضًا بادئة لكلمة واحدة على الأقل من الكلمات المستهدفة.
لكل حالة \(s\) ولكل حرف تالٍ \(\sigma\in\{A,E,F,R\}\) يوجد انتقال حتمي
$$\delta(s,\sigma).$$
وتحمل كل حالة كذلك متجه خرج
$$m(s)=\bigl(m_1(s),m_2(s),m_3(s),m_4(s)\bigr),$$
حيث يعبّر \(m_i(s)\) عن عدد المرات التي ينتهي فيها النمط رقم \(i\) عند الوصول إلى الحالة \(s\)، بعد دمج المخارج الموروثة عبر روابط الفشل. بهذه الطريقة يعرف الانتقال الواحد جميع المطابقات الجديدة التي انتهت في هذه الخطوة، حتى لو جاءت بسبب التداخل بين الأنماط.
لبادئة طولها \(\ell\)، نعرّف
$$D_\ell\bigl(s,c_1,c_2,c_3,c_4\bigr)$$
على أنه عدد البوادئ ذات الطول \(\ell\) التي تنتهي في الحالة \(s\) والتي تملك عدادات مقصوصة \(c_i\in\{0,1,2\}\) لمرات ظهور الأنماط الأربعة.
وهنا يكون \(c_i=0\) إذا لم يظهر النمط بعد، ويكون \(c_i=1\) إذا ظهر مرة واحدة تمامًا.
أما \(c_i=2\) فيعني أن النمط ظهر مرتين على الأقل.
هذا القص عند القيمة \(2\) كافٍ تمامًا، لأن أي مسار يصل فيه أحد العدادين إلى \(2\) لا يمكن أن يساهم في الجواب النهائي. لا حاجة بعد ذلك إلى التمييز بين «مرتين» و«ثلاث مرات أو أكثر».
شرط البداية هو
$$D_0(0,0,0,0,0)=1,$$
وجميع الحالات الأخرى تبدأ بقيمة \(0\).
إذا كانت بادئة بطول \(\ell\) تُحسب ضمن \(D_\ell(s,c_1,c_2,c_3,c_4)\)، ثم أضفنا حرفًا واحدًا \(\sigma\)، فإن الأوتوماتون ينتقل إلى
$$s'=\delta(s,\sigma).$$
وتصبح العدادات المقصوصة الجديدة
$$c_i'=\min\bigl(2,\;c_i+m_i(s')\bigr)\qquad (1\le i\le 4).$$
إذا صار أي \(c_i'=2\)، فإن هذا الفرع يُرفض فورًا. وإلا فإننا نضيف
$$D_\ell(s,c_1,c_2,c_3,c_4)$$
إلى
$$D_{\ell+1}(s',c_1',c_2',c_3',c_4').$$
هذه العلاقة دقيقة تمامًا، لأن إضافة حرف واحد لا تغيّر ما يهم مستقبلًا إلا من خلال حالة الأوتوماتون الجديدة وملف الظهورات المحدّث.
الهدف هو أن يظهر كل نمط مرة واحدة بالضبط. لذلك لا بد أن تنتهي أي كلمة صالحة بالملف
$$\bigl(1,1,1,1\bigr).$$
إذا وصل أحد المكوّنات أثناء السير إلى القيمة \(2\)، فهذا يعني أن أحد الأنماط ظهر مرتين على الأقل، ولا يمكن لأي أحرف لاحقة أن تصلح ذلك. لذا فاستبعاد هذه الحالة ليس تقريبًا أو حيلةً، بل خطوة منطقية مكافئة تمامًا لإزالة المسارات المستحيلة.
وهذه الفكرة هي التي تجعل فضاء الحالات صغيرًا: لكل حالة في الأوتوماتون لا نحتاج إلا إلى \(3^4=81\) ملف ظهورات ممكنًا.
بعد معالجة الحروف \(n\) كلها، نجمع على جميع حالات الأوتوماتون التي تملك الملف الهدف تمامًا:
$$\boxed{F(n)=\sum_s D_n\bigl(s,1,1,1,1\bigr).}$$
ولا حاجة إلى أي حد تصحيحي إضافي. فقاعدة الانتقال فرضت مسبقًا شرط «على الأكثر مرة واحدة»، والملف النهائي يفرض شرط «مرة واحدة على الأقل»، ومحصلة الشرطين هي «مرة واحدة بالضبط».
من الأمثلة الصحيحة الملموسة الكلمة
$$\text{FREEFAREA}.$$
والسلاسل الفرعية المهمة ذات الطول \(4\) فيها هي
$$\text{FREE},\ \text{REEF},\ \text{FARE},\ \text{AREA},$$
وكل واحدة منها تظهر مرة واحدة فقط. أما ملف الظهورات فيتطور كما يلي:
بعد قراءة \(\text{FREE}\): \((1,0,0,0)\).
بعد قراءة \(\text{FREEF}\): \((1,0,0,1)\).
بعد قراءة \(\text{FREEFARE}\): \((1,1,0,1)\).
بعد قراءة \(\text{FREEFAREA}\): \((1,1,1,1)\).
وتتأكد التطبيقات كذلك من القيمة المرجعية
$$F(9)=1,$$
لذلك فهذا المثال ليس صالحًا فحسب، بل هو الكلمة الوحيدة الصالحة عندما يكون الطول \(9\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها تمامًا. تبدأ ببناء trie للأنماط الأربعة، ثم تحسب روابط الفشل باستخدام مرور بعرض الشجرة. وأثناء ذلك تُدمَج معلومات الخرج الموروثة من سلف الفشل داخل كل حالة، بحيث يعرف كل انتقال لاحقًا أي الأنماط انتهت في هذه الخطوة.
بعد ذلك تخصص الشيفرة طبقتين متناوبتين من البرمجة الديناميكية. كل حالة من حالات الأوتوماتون تُقرن بأحد ملفات الظهورات المقصوصة وعددها \(81\)، لذا فإن كل طبقة تكون مجرد جدول مسطح مفهرس بحسب «حالة الأوتوماتون + الملف». طبقة البداية تحتوي طريقة واحدة فقط: السلسلة الفارغة عند الجذر مع أربعة أصفار.
ثم تتقدم الشيفرة عبر \(30\) موضعًا. في كل موضع تُفحَص جميع الخانات غير الصفرية في الطبقة الحالية، وتُجرَّب الأحرف الأربعة الممكنة، ويُتّبع انتقال الأوتوماتون المحسوب مسبقًا، وتُحدَّث العدادات الأربعة بعد القص؛ فإذا أدى الانتقال إلى عدّ أحد الأنماط للمرة الثانية رُفض ذلك الفرع مباشرة. وإلا أُضيف عدد الطرق إلى الخانة المناسبة في الطبقة التالية.
بعد الموضع الأخير، تجمع الشيفرة جميع الخانات التي تملك الملف \((1,1,1,1)\) بالضبط. كما أن نسخة C++ تحتوي على اختبارين صغيرين للصحة هما \(F(9)=1\) و\(F(15)=72863\) قبل إنتاج قيمة \(F(30)\).
إذا رمزنا إلى عدد حالات الأوتوماتون بـ \(S\)، فإن بناء الأوتوماتون وروابط الفشل يكلف \(O(S\cdot 4)\) لأن حجم الأبجدية يساوي \(4\). أما البرمجة الديناميكية فتجري
$$O\bigl(n\cdot S\cdot 3^4\cdot 4\bigr)$$
عملية، لأنها في كل موضع تمر على جميع الحالات، وجميع ملفات الظهورات المقصوصة، والأحرف الأربعة الممكنة.
وباستخدام طبقتين متناوبتين فقط، يبقى استهلاك الذاكرة عند
$$O(S\cdot 3^4).$$
وفي هذه المسألة بالذات يكون الثابت صغيرًا جدًا: trie الخاص بالكلمات الأربع ذات الطول \(4\) يحتوي فقط على \(16\) حالة، وبالتالي فكل طبقة من طبقات DP تحتوي \(16\cdot 81=1296\) خانة فقط. ولهذا يصبح الحساب الدقيق لقيمة \(n=30\) سهلًا بمجرد صياغة الحالة على النحو الصحيح.