Kalıplar kümesi için Aho — Corasick otomatını inşa edelim. Kalıpların toplam uzunluğu 5 \cdot 10^5'i geçmez, dolayısıyla trie en fazla 5 \cdot 10^5 + 1 köşe içerir. Alfabe küçük Latin harfinden oluşur. Bir kalıbın bittiği köşe terminal olarak işaretlenir ve her kalıbı için bitiş köşesinin numarasını olarak saklarız. Eşit kalıplar aynı köşede biter.
Metnin işlenmesi. Metni otomat üzerinden geçirelim. Diyelim ki bir sonraki karakteri okuduktan sonra otomat köşesindedir. O zaman v \to \mathit{link}[v] \to \ldots \to 0 sonek bağlantıları zinciri üzerindeki köşeler, şimdiye kadar okunan metnin kalıpların öneki olan tüm soneklerine karşılık gelir. Bir kalıbın şu anki pozisyonda metinde bitecek şekilde geçmesi, ancak ve ancak bitiş köşesinin bu zincir üzerinde yer alması halinde mümkündür. Bu nedenle, sonek bağlantıları zincirlerinin geçtiği tüm köşeleri bayrağıyla işaretlemek yeterlidir. kalıbı için cevap, değeridir.
Zincirin tamamının neden dolaşılamayacağı. Bir zincirin uzunluğu kalıp uzunluğu mertebesinde olabilir. Örneğin, , , , kalıpları ve metni için, her pozisyonda uzun bir zincirin dolaşılması gerekecek ve toplam süre O(n \cdot L) olacaktır; burada en uzun kalıbın uzunluğudur. Bu nedenle zincir dolaşımı iki durumda durdurulur:
\mathit{term}[u] = \textbf{\textit{false}}: \mathit{term}[u] = \mathit{term}[u] \lor \mathit{term}[\mathit{link}[u]] bayrağı otomat inşa edilirken hesaplanır ve 'dan başlayan zincirde en az bir terminal köşe bulunduğu anlamına gelir. Eğer false ise, zincirin devamında kalıp bitişi yoktur;
\mathit{vis}[u] = \textbf{\textit{true}}: köşesi daha önce ziyaret edilmiştir ve bu durumda 'dan \mathit{term} = \textbf{\textit{false}} olan ilk köşeye kadar olan zincirin tamamı da zaten dolaşılmıştır.
İkinci ifade, köşesi işaretlendiğinde dolaşımın her zaman onun sonek bağlantısı boyunca devam etmesi ve yalnızca \mathit{term} = \textbf{\textit{false}} olan bir köşede ya da zaten işaretlenmiş bir köşede durması nedeniyle doğrudur. Böylece her köşe en fazla bir kez işaretlenir.
Karmaşıklık. Otomatın inşası O(V \cdot 26) sürer; burada V \le 5 \cdot 10^5 + 1 trie köşelerinin sayısıdır. Metnin işlenmesi geçiş artı işaretleme alır ve cevaplar sürede yazdırılır. Geçiş dizisi yaklaşık 5 \cdot 10^5 \cdot 26 \cdot 4 bayt MB tutar.
Örnek
Metin , kalıplar , , . Kalıpları verilen sırayla trie'ye ekleyelim. Köşe numaraları oluşturulma sırasına karşılık gelir, her köşenin altında onun string'i yazılıdır ve terminal köşeler vurgulanmıştır: \mathit{endNode} = (3, 6, 9).
Köke gitmeyen sonek bağlantıları:
\mathit{link}(ba) = a, yani \mathit{link}[2] = 4;
\mathit{link}(ab) = b, yani \mathit{link}[5] = 1;
\mathit{link}(bab) = ab, yani \mathit{link}[3] = 5;
\mathit{link}(ayb) = b, yani \mathit{link}[8] = 1;
\mathit{link}(ayba) = ba, yani \mathit{link}[9] = 2.
Hiçbir sonek bağlantısı terminal bir köşeye gitmez, dolayısıyla \mathit{term} = \textbf{\textit{true}} yalnızca , ve köşelerinde geçerlidir.
Metni otomat üzerinden geçirelim. Her karakterin altında, o karakter okunduktan sonra otomatın bulunduğu köşe gösterilmiştir.
char | vertex string | marked vertices | ||
0 | 4 | — | ||
1 | 7 | — | ||
2 | 8 | — | ||
3 | 9 | 9 () | ||
4 | 3 | 3 () | ||
5 | 0 | — | ||
6 | 0 | — |
İndeksi olan karakterden sonra otomat terminal köşe 'dadır (): bu köşe işaretlenir ve zincir dolaşımı \mathit{link}[9] = 2 köşesinde durur, çünkü bu köşe için \mathit{term}[2] = \textbf{\textit{false}}'dır. Bir sonraki karakter 'dir: trie'de köşesinden ile bir geçiş yoktur ve sonek bağlantısı aracılığıyla otomat \mathit{go}[2][b] = 3 köşesine geçer (), bu köşe de işaretlenir. köşesi () hiçbir zaman işaretlenmez.
Cevap: \mathit{vis}[3] = \textbf{\textit{true}}, \mathit{vis}[6] = \textbf{\textit{false}}, \mathit{vis}[9] = \textbf{\textit{true}}, yani YES, NO, YES.
Dolaşımın bayrağıyla durdurulması. , , kalıplarını ve metnini ele alalım. Trie, (), (), () köşelerinden oluşan bir zincirdir, hepsi terminaldir ve sonek bağlantıları 3 \to 2 \to 1 \to 0 şeklinde gider.
step | chain traversal | marked | |
1 | 1 | 1 \to 0 (\mathit{term}[0] = \textit{false}) | 1 |
2 | 2 | 2 \to 1 (\mathit{vis}[1] = \textit{true}) | 2 |
3 | 3 | 3 \to 2 (\mathit{vis}[2] = \textit{true}) | 3 |
4 | 3 | (\mathit{vis}[3] = \textit{true}) | — |
Her köşe tam olarak bir kez işaretlenir. bayrağı olmasaydı, ikinci adımdan itibaren her seferinde zincirin yeniden köke kadar dolaşılması gerekirdi.
Algoritmanın Uygulanması
Sabitleri tanımlayalım: alfabe boyutu ve maksimum trie köşe sayısı.
const int ALPH = 26;
const int MAXN = 500000 + 5;dizisi otomatın geçişlerini, ise sonek bağlantılarını saklar. bayrağı, köşesinden sonek bağlantıları aracılığıyla bir kalıbın bitişine ulaşılabileceği anlamına gelir, ise köşesinin metin işlenirken daha önce ziyaret edildiği anlamına gelir. değişkeni mevcut köşe sayısını içerir; kök köşesidir.
int go_[MAXN][ALPH];
int link_[MAXN];
bool term[MAXN], vis[MAXN];
int sz = 1;addString fonksiyonu kalıbını trie'ye ekler ve bittiği köşenin numarasını döndürür.
int addString(const string &s)
{
int v = 0;
for (char ch : s)
{
int c = ch - 'a';
if (!go_[v][c]) go_[v][c] = sz++;
v = go_[v][c];
}
term[v] = true;
return v;
}buildAutomaton fonksiyonu genişlik öncelikli arama kullanarak sonek bağlantılarını hesaplar, otomatın geçişlerini tamamlar ve bayraklarını hesaplar. Trie'nin kökünü kuyruğa ekleyelim.
void buildAutomaton()
{
queue<int> q;
q.push(0);Kuyruktan bir köşesi çıkaralım. köşesi daha önce işlenmiştir, dolayısıyla onun bayrağı zaten nihaidir ve bayrağı \mathit{term}[\mathit{link\_}[v]] bayrağıyla tamamlanır.
while (!q.empty())
{
int v = q.front(); q.pop();
term[v] = term[v] || term[link_[v]];Tüm karakterleri üzerinde dolaşalım. Eğer trie'de v \to u geçişi karakteri ile mevcutsa, o zaman köşesinin sonek bağlantısı \mathit{go\_}[\mathit{link\_}[v]][c]'ye eşittir (kökün çocukları için bu kök olur) ve köşesi kuyruğa eklenir.
for (int c = 0; c < ALPH; c++)
{
int u = go_[v][c];
if (u)
{
link_[u] = (v == 0) ? 0 : go_[link_[v]][c];
q.push(u);
}Eğer trie'de geçiş yoksa, tamamlanır: köşesinden karakteri ile otomat, 'den gidilen köşenin aynısına gider. Kökten eksik bir geçiş köke gider.
else
go_[v][c] = (v == 0) ? 0 : go_[link_[v]][c];
}
}
}Programın ana kısmı. Metni ve kalıp sayısı 'yi okuyalım.
cin >> text >> k;Kalıpları okuyalım, trie'ye ekleyelim ve bitiş köşelerinin numaralarını dizisinde saklayalım.
vector<int> endNode(k);
string p;
for (int i = 0; i < k; i++)
{
cin >> p;
endNode[i] = addString(p);
}Aho — Corasick otomatını inşa edelim.
buildAutomaton();Metni otomat üzerinden geçirelim.
int v = 0;
for (char ch : text)
{
v = go_[v][ch - 'a'];Her geçişten sonra, mevcut köşesinden sonek bağlantıları zinciri boyunca ilerleyip köşeleri işaretleyelim. Dolaşım, zincirin geri kalanında kalıp bitişi yoksa (\mathit{term}[u] = \textbf{\textit{false}}) ya da köşesi zaten işaretliyse durur.
for (int u = v; term[u] && !vis[u]; u = link_[u])
vis[u] = true;
}kalıbı, ancak ve ancak bitiş köşesi işaretliyse metinde geçmektedir.
for (int i = 0; i < k; i++)
cout << (vis[endNode[i]] ? "YES" : "NO") << '\n';