Eğer kümesindeki her dize için her bir deseni ayrı ayrı arasaydık, toplam girdi boyutu MB'a ve desene kadar çıkabileceğinden çok fazla işlem yapmamız gerekirdi. kümesi için Aho — Corasick otomatını inşa edelim ve 'deki her dizeyi karakterleri üzerinde tek bir geçişte kontrol edelim.
Trie. Tüm desenleri bir trie'a ekleyin. Dizeler, kodları ile arasında olan ASCII karakterlerinden oluşur, bu yüzden geçişler karakter kodu ile doğrudan indekslenen boyutunda bir dizide saklanır. En fazla desen vardır, her biri en fazla uzunluğundadır; dolayısıyla trie en fazla 100 \cdot 80 + 1 köşeye sahiptir. Bir desenin bittiği köşe terminal olarak işaretlenir.
Otomat. Genişlik öncelikli arama kullanarak, sonek bağlantılarını hesaplıyor ve otomatın geçişlerini tamamlıyoruz: \mathit{go}[v][c], otomatın 'den karakteriyle geçtiği köşedir. Bundan sonra, her köşenin herhangi bir karakterle bir geçişi vardır ve bir dizeyi işlerken sonek bağlantılarını takip etmeye gerek yoktur.
bayrağı. Otomatın şu ana kadar okuduğu dize, ancak ve ancak mevcut köşeden sonek bağlantıları zinciri boyunca bir terminal köşeye ulaşılabiliyorsa, bazı desenlerle biter. Bu nedenle, her köşe için bayrağı hesaplıyoruz
Köşeler genişlik öncelikli sırada işlenir ve köşesi 'den köke daha yakındır, bu yüzden işlendiğinde, \mathit{term}[\mathit{link}[v]] değeri zaten kesinleşmiştir.
Bir dizeyi kontrol etme. 'deki bir sonraki dize için kökten başlıyoruz ve karakterleri boyunca ilerliyoruz. Eğer bir geçişten sonra \mathit{term}[v] = \textbf{\textit{true}} olan bir köşedeysek, o zaman az önce okunan dizenin öneki bazı desenlerle biter, yani dize bir deseni alt dize olarak içerir. Kalan karakterlerin okunmasına gerek yoktur: dize yazdırılır. Dize sonuna kadar okunmuşsa ve bayrak hiç karşılaşılmamışsa, hiçbir desen içermiyordur.
Girdi. kümesindeki dizeler boşluk içerebilir, bu yüzden getline fonksiyonuyla okunurlar. sayısı okunduktan sonra, ilk satırın geri kalanı okunmalıdır. Boş bir dize boş olmayan bir deseni içeremez, bu yüzden hiçbir zaman yazdırılmaz.
Karmaşıklık. Otomatın inşası O(V \cdot 128) sürer, burada V \le 8001 trie köşelerinin sayısıdır. 'deki her dize, uzunluğuyla orantılı bir sürede işlenir, bu yüzden tüm arama sürede çalışır, burada girdinin toplam boyutudur. Geçiş dizisi yaklaşık 8001 \cdot 128 \cdot 4 bayt MB yer kaplar.
Örnek
Desen kümesi T = \{abc, bca, aba, bcc, aac\}'dir. Desenleri verilen sırayla trie'a ekleyin. Köşe numaraları oluşturulma sırasına karşılık gelir; her köşenin altında karşılık geldiği dize yazılıdır. Terminal köşeler vurgulanmıştır ve yanlarında ilgili desen gösterilmiştir.
Sonek bağlantılarını hesaplayalım. Bir köşenin sonek bağlantısı, dizesinin trie'da bulunan en uzun has sonekine karşılık gelen köşeye götürür:
\mathit{link}(ab) = b, yani \mathit{link}[2] = 4;
\mathit{link}(aa) = a, yani \mathit{link}[9] = 1;
\mathit{link}(abc) = bc, yani \mathit{link}[3] = 5;
\mathit{link}(aba) = a: soneki trie'da yoktur, bu yüzden \mathit{link}[7] = 1;
\mathit{link}(bca) = a: soneki trie'da yoktur, bu yüzden \mathit{link}[6] = 1;
, , , ve köşeleri için, trie'da hiçbir has, boş olmayan sonek bulunmadığından, sonek bağlantıları köke götürür.
Hiçbir sonek bağlantısı bir terminal köşeye götürmez, bu yüzden bayrakları desen bitiş işaretleriyle çakışır: \mathit{term} = \textbf{\textit{true}} yalnızca , , , ve köşelerinde geçerlidir.
Tablo, sonek bağlantılarını, bayraklarını ve , , karakterleriyle otomatın geçişlerini göstermektedir. Trie'da bulunmayan geçişler sonek bağlantıları kullanılarak tamamlanır. Diğer tüm karakterlerle, otomat herhangi bir köşeden köke geçer.
dize | \boldsymbol{\mathit{go}['a']} | \boldsymbol{\mathit{go}['b']} | \boldsymbol{\mathit{go}['c']} | |||
0 | 0 | false | 1 | 4 | 0 | |
1 | 0 | false | 9 | 2 | 0 | |
2 | 4 | false | 7 | 4 | 3 | |
3 | 5 | true | 6 | 4 | 8 | |
4 | 0 | false | 1 | 4 | 5 | |
5 | 0 | false | 6 | 4 | 8 | |
6 | 1 | true | 9 | 2 | 0 | |
7 | 1 | true | 9 | 2 | 0 | |
8 | 0 | true | 1 | 4 | 0 | |
9 | 1 | false | 9 | 2 | 10 | |
10 | 0 | true | 1 | 4 | 0 |
Örneğin, trie'da köşesinden () karakteriyle bir geçiş yoktur. Otomat, \mathit{link}[9] = 1 () köşesinden geçişi alır: \mathit{go}[9][b] = \mathit{go}[1][b] = 2. Gerçekten de, okunduktan sonra, bazı desenlerin öneki olan en uzun sonek 'dir.
kümesindeki dizeleri otomattan geçirelim. Her karakterin altında, onu okuduktan sonra otomatın ulaştığı köşe gösterilmiştir.
: otomat , , , , , , köşelerinden geçer. Bunlardan hiçbiri terminal olmadığından, dize yazdırılmaz.
: okunduktan sonra otomat () köşesindedir ve karakteriyle, \mathit{term} = \textbf{\textit{true}} olan () köşesine geçer. Dize desenini içerir ve yazdırılır; kalan karakterler okunmaz.
: köşeler , , , , , 'dir; hiçbir desen bulunmaz.
: 'den sonra otomat () köşesindedir ve karakteriyle terminal () köşesine geçer. Dize yazdırılır.
Cevap ve dizelerinden oluşur.
Algoritmanın Uygulanması
Sabitleri tanımlayın. Otomatın alfabesi karakterden oluşur ve karakter kodları indeks olarak kullanılır. Maksimum trie köşe sayısı 100 \cdot 80 artı küçük bir rezervdir.
const int ALPH = 128; // ASCII kodları 32..126
const int MAXN = 100 * 80 + 5; // maksimum trie köşe sayısıdizisi otomatın geçişlerini saklar, sonek bağlantılarını saklar ve , köşesinden bir desenin bitişine sonek bağlantıları üzerinden ulaşılabildiği bayrağıdır. değişkeni mevcut köşe sayısını içerir; kök köşesidir. Global diziler başlangıçta sıfırlarla doldurulur, bu yüzden trie'da \mathit{go\_}[v][c]'nin sıfır değeri, bir geçiş olmadığı anlamına gelir.
int go_[MAXN][ALPH]; // otomatın geçişleri
int link_[MAXN]; // sonek bağlantıları
bool term[MAXN]; // köşeden bir desenin bitişine
// ulaşılabilir
int sz = 1; // köşe sayısı, 0 köktüraddString fonksiyonu desenini trie'a ekler. Kodunun negatif olmayan bir indeks olarak kullanılması için bir karakter unsigned char olarak işlenir. Karakterle bir geçiş yoksa, yeni bir köşe oluşturulur. Desenin bittiği köşede, bayrağı ayarlanır.
void addString(const string &s)
{
int v = 0;
for (unsigned char c : s)
{
if (!go_[v][c]) go_[v][c] = sz++;
v = go_[v][c];
}
term[v] = true;
}buildAutomaton fonksiyonu, genişlik öncelikli arama kullanarak sonek bağlantılarını hesaplar ve otomatın geçişlerini tamamlar.
void buildAutomaton()
{
queue<int> q;Trie'nin kökünü (köşe numarası ) kuyruğa ekleyin. Genişlik öncelikli arama oradan başlar.
q.push(0);Kuyruktan bir köşesi çıkarın. Sonek bağlantısı zaten hesaplanmıştır ve köşesi daha önce işlenmiştir, bu yüzden bayrağı hemen köşesinin bayrağıyla tamamlanabilir.
while (!q.empty())
{
int v = q.front(); q.pop();
term[v] = term[v] || term[link_[v]];Tüm karakterleri üzerinde yineleme yapın. Trie'da v \to u geçişi karakteriyle varsa, köşesinin sonek bağlantısı \mathit{go\_}[\mathit{link\_}[v]][c]'ye eşittir (kökün çocukları için bu köktür) 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);
}Trie'da bir geçiş yoksa, tamamlanır: köşesinden karakteriyle otomat, 'den geçtiği aynı köşeye geçer. Kökten, eksik bir geçiş köke götürür.
else
go_[v][c] = (v == 0) ? 0 : go_[link_[v]][c];
}
}
}Programın ana kısmı. Desen sayısı 'yi okuyun ve ardından sayısını içeren satırın geri kalanını okumak için getline fonksiyonunu kullanın.
cin >> n;
getline(cin, line); // n sayısını içeren satırın geri kalanını okuDesenleri okuyun ve boş olmayanları trie'a ekleyin.
for (int i = 0; i < n; i++)
{
getline(cin, line);
if (!line.empty()) addString(line);
}Aho — Corasick otomatını inşa edin.
buildAutomaton();kümesindeki dizeleri girdinin sonuna kadar okuyun. Her dize için kökten başlıyoruz; bayrağı, içinde bir desen bulunup bulunmadığını gösterir.
while (getline(cin, line))
{
int v = 0;
bool found = false;Dizenin karakterleri üzerinde gezinin. ve üzeri kodlara sahip karakterler otomatta temsil edilmez (ifadeye göre, girdide bulunmazlar); eğer görünürlerse, otomat köke geri döner. Otomat bayrağı olan bir köşeye ulaşır ulaşmaz, dize bir desen içerir ve dizenin taranması durur.
for (unsigned char c : line)
{
v = go_[v][c];
if (term[v]) { found = true; break; }
}Bir desen bulunursa, dizeyi yazdırın.
if (found) cout << line << '\n';
}