Алгоритм Касаи

Алгоритм Касаи (Аримуры — Арикавы — Касаи — Ли — Пака) — алгоритм, за линейное время находящий длины наибольших общих префиксов (англ. lcp, longest common prefix) у всех пар суффиксов данной строки, соседних в лексикографическом порядке (то есть у всех соседних элементов суффиксного массива). Входом алгоритма являются сама строка и суффиксный массив, выходом — массив длин наибольших общих префиксов.

Реализация алгоритма на языке Java

public class Kasai {

	// в sufArray (s.length() + 1) элементов — включая пустой суффикс
	public static int[] solve(String s, String[] sufArray) {
		int pos[] = new int[s.length() + 1];
		for (int i = 0; i <= s.length(); i++) {
			pos[i] = s.length() - sufArray[i].length() + 1;
		}
		int rank[] = new int[s.length() + 1];
		for (int i = 0; i <= s.length(); i++) {
			rank[pos[i]] = i;
		}
		int ans[] = new int[s.length() + 1];
		int h = 0;
		for (int i = 1; i <= s.length(); i++) {
			if (rank[i] > 1) {
				int k = pos[rank[i] - 1];
				while (((i + h - 1) != s.length())
						&& ((k + h - 1) != s.length())
						&& (s.charAt(i + h - 1) == s.charAt(k + h - 1)))
					h++;
				ans[rank[i]] = h;
				if (h > 0)
					h--;
			}
		}
		return ans; // ans[i + 1] = длина наибольшего общего префикса sufArray[i] и sufArray[i - 1]
	}
}

Реализация на языке C++

// Эта реализация предполагает наличие в конце строки text символа, отличного от всех остальных ("терминальный символ").
// Обратите внимание, что реализация алгоритма заметно отличается от предыдущей.

void solve(const std::string& text, const std::vector<int>& pos, std::vector<int>& lcp)
{
	int n = text.length();
	std::vector<int> rank(n);
	for (int i = 0; i < n; ++i) rank[pos[i]] = i;
	for (int i = 0, k = 0; i < n; ++i)
	{
		if (k > 0) k--;
		if (rank[i] == n - 1)
                { 
                    lcp[n - 1] = -1, k = 0; 
                    continue;
                }
		int j = pos[rank[i] + 1];
		while (max(i + k, j + k) < text.length() && text[i + k] == text[j + k]) k++;
		lcp[rank[i]] = k;
	}
	// lcp[x] - длина наибольшего общего префикса суффиксов pos[x] и pos[x + 1] 
}

Примечания

Литература

  • Kasai, Toru and Lee, Gunho and Arimura, Hiroki and Arikawa, Setsuo and Park, Kunsoo (2001). "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications". Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching. CPM '01. Springer-Verlag. pp. 181--192. Kasai:2001:LLC:647820.736222. Дата обращения: 6 декабря 2013.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  • Guigo, R. and Gusfield, D. Algorithms in Bioinformatics: Second International Workshop, WABI 2002, Rome, Italy, September 17-21, 2002, Proceedings. — Springer, 2002. — P. 453-455. — ISBN 9783540442110.

Read other articles:

Crash Course (web series)

Educational YouTube channel Crash CourseCrash Course YouTube channel iconGenreEducational[1]Created byJohn Green Hank GreenDeveloped by Complexly PBS Digital Studios Written byVariousDirected by Stan Muller Nicholas Jenkins Brandon Brungard Nicole Sweeney Hannah Bodenhausen Creative directorThought Café (Formerly Thought Bubble)Presented by List of presenters John GreenHank GreenPhil PlaitCraig BenzineStan MullerAdriene HillJacob CliffordShini SomaraAndre MeadowsCarrie Anne PhilbinMi...

 

Linda Hardy

Linda HardyHardy in 2014Lahir11 Oktober 1973 (umur 50)Nantes, Loire-Atlantique, FrancePekerjaanActress, model Linda Hardy (lahir 11 Oktober 1973) adalah model dan aktris berkebangsaan Prancis. Hardy memenangi gelar sebagai Miss Prancis pada tahun 1992 dan mewakili negaranya untuk mengikuti kontes Miss Universe 1992 dan Miss World 1992. Kemudian dia menjalani kariernya sebagai aktris di ranah perfilman Prancis, memulai pada tahun 1999 melalui film Recto/Verso, yang kemudian diikuti denga...

 

Kristina Persson

Kristina Persson Menteri Kooperasi NordikPetahanaMulai menjabat 3 Oktober 2014Penguasa monarkiCarl XVI GustafPerdana MenteriStefan Löfven PendahuluEwa BjörlingPenggantiPetahanaMenteri Pengembangan StrategiPetahanaMulai menjabat 3 Oktober 2014Penguasa monarkiCarl XVI GustafPerdana MenteriStefan Löfven PendahuluJabatan dibentukPenggantiPetahana Informasi pribadiLahir16 April 1945 (umur 78)Östersund, SwediaPartai politikDemokrat SosialPekerjaanAhli ekonomiSunting kotak info ...

Teton County, Wyoming

County in Wyoming, United States County in WyomingTeton CountyCountyGeorge Washington Memorial Park (Jackson, Wyoming) FlagLocation within the U.S. state of WyomingWyoming's location within the U.S.Coordinates: 43°55′N 110°34′W / 43.92°N 110.57°W / 43.92; -110.57Country United StatesState WyomingFoundedFebruary 15, 1921 (authorized)1922 (organized)Named forTeton RangeSeatJacksonLargest townJacksonArea • Total4,216 sq mi (10,920&#...

 

The Man of the Woods Tour

2018–19 concert tour by Justin Timberlake The Man of the Woods TourTour by Justin TimberlakeLocation Europe North America Associated albumMan of the WoodsStart dateMarch 13, 2018 (2018-03-13)End dateApril 13, 2019 (2019-04-13)Legs3No. of shows115Supporting acts Bazzi Choppa Francesco Yates The Shadowboxers Attendance1.75 million[1]Box office$226.3 million[1]Justin Timberlake concert chronology The 20/20 Experience World Tour(2013–15) The Man ...

 

Gösta Cederlund

Gösta CederlundLahir(1888-03-06)6 Maret 1888Stockholm, SwediaMeninggal4 Desember 1980(1980-12-04) (umur 92)Tahun aktif1907–1975Suami/istri1). Ingeborg Elisabeth Magni (1914–1930) ; 2). Anna-Lisa Ryding (1932–1980). (hingga kematiannya) Gösta Cederlund, Gustaf (Gösta) Edvard Cederlund, (6 Maret 1888 – 4 Desember 1980) adalah sworang sutradara, dan aktor asal Swedia. Ia dikenal sebagai aktor mulai 1930an hingga 1950an. Film pilihan A Dangerous Wooing (19...

Telenești

Town in Telenești District, Moldova Place in MoldovaTelenești FlagSealTeleneștiLocation within MoldovaCoordinates: 47°30′10″N 28°22′0″E / 47.50278°N 28.36667°E / 47.50278; 28.36667CountryMoldovaRaion (district)TeleneștiArea • Total536 km2 (207 sq mi)Elevation96 m (315 ft)Population (2014)[1] • Total7,227 • Density13/km2 (35/sq mi)Time zoneUTC+2 (EET) • Summer (DS...

 

Maritime history of the United Kingdom

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Maritime history of the United Kingdom – news · newspapers · books · scholar · JSTOR (October 2022) (Learn how and when to remove this message) The Maritime history of the United Kingdom involves events including shipping, ports, navigation, and seamen, as well...

 

Dolar Brunei

Untuk kegunaan lain, lihat Dolar. Dolar BruneiRinggit Brunei Darussalam (Melayu)ريڠڬيت بروني Jawi MelayuUang kertas dolar Brunei Darussalam seri 1996.ISO 4217KodeBNDDenominasiSubsatuan 1/100senSimbolB$Uang kertas Sering digunakan$1, $5, $10, $50, $100 Jarang digunakan$20, $25, $500, $1,000, $10,000Uang koin1, 5, 10, 20, 50 senDemografiPengguna Brunei SingapuraEmisiBank sentralAutoriti Monetari Brunei Darussalam Situs webhttp://www.ambd.gov.bn/ValuasiInflasi2...

Halte Transjakarta Kampung Melayu

518 714 1116 Kampung Melayu Halte TransjakartaAkses Masuk Pintu A Halte Kampung Melayu, 2023LetakKotaJakarta TimurDesa/kelurahanBali Mester, JatinegaraKodepos13310AlamatJalan Oto Iskandar di NataKoordinat6°13′28″S 106°52′00″E / 6.2244°S 106.8667°E / -6.2244; 106.8667Koordinat: 6°13′28″S 106°52′00″E / 6.2244°S 106.8667°E / -6.2244; 106.8667Desain HalteStruktur BRT, median jalan bebas 1 tengah Pintu masukMelalui Termi...

 

Randall Road

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Randall Road – news · newspapers · books · scholar · JSTOR (February 2015) (Learn how and when to remove this message) Randall RoadNorman Randall Memorial HighwayLength31.4 mi (50.5 km)LocationCrystal Lake, Lake in the Hills, Algonquin, Carpentersvill...

 

Salaberry Armoury

Drill Hall / armoury in Gatineau, QuebecSalaberry ArmouryManège militaire SalaberryThe Salaberry ArmouryGeneral informationTypeDrill Hall / armouryArchitectural stylelate Château StyleAddress188, boulevard Alexandre-TachéGatineau, QuebecJ9A 1L8Current tenantsRégiment de HullConstruction started1930sCompleted1938/01/01ClientCanadian ArmyOwnerCanadian Forces Crown OwnedDimensionsOther dimensions2.0800 ha (5.140 acres)Technical detailsStructural systemsteeply pitched gable roofFloor ar...

العلاقات الزامبية السورية

العلاقات الزامبية السورية زامبيا سوريا   زامبيا   سوريا تعديل مصدري - تعديل   العلاقات الزامبية السورية هي العلاقات الثنائية التي تجمع بين زامبيا وسوريا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة زامبيا سو...

 

Falcade

FalcadeKomuneComune di FalcadeNegaraItaliaWilayahVenetoProvinsiProvinsi Belluno (BL)FrazioniSappade, Caviola, Valt, Coste, Somor, Le fratte, Marmolada, Tabiadon di Canes, Tabiadon di ValLuas • Total53,2 km2 (205 sq mi)Ketinggian1.165 m (3,822 ft)Populasi (Desember 2004) • Total2.175 • Kepadatan4,1/km2 (11/sq mi)DemonimFalcadiniZona waktuUTC+1 (CET) • Musim panas (DST)UTC+2 (CEST)Kode pos32020Kode area telepon04...

 

List of railway museums in the United Kingdom

The National Railway Museum, York is the largest railway museum in the United Kingdom This is a list of railway museums in the United Kingdom. England Amberley Working Museum, Arundel, West Sussex Astley Green Colliery Museum, Astley, Greater Manchester Bahamas Locomotive Society Barrow Hill Roundhouse Beamish museum Bere Ferrers railway station Bideford Railway Heritage Centre, Devon Bishop's Castle Railway Museum Bressingham Steam Museum, Norfolk Bristol Harbour Railway and Industrial Muse...

Francis Bok

Former Sudanese slave, abolitionist (born 1979) Francis BokBornFebruary 1979 (age 45)SudanOccupations State Minister of Information, Youth and Sports for Lol State, South Sudan,[citation needed] author abolitionist SpouseAtakChildrenBuk and DhalParent(s)Bol Buk Dol and Adut Al Akok Francis Piol Bol Bok (born February 1979), a Dinka tribesman and citizen of South Sudan, was a slave for ten years and later became an abolitionist and author living in the United States. Biograph...

 

Fuentes de Andalucía

Peta Fuentes de Andalucia (2009). Fuentes de Andalucía merupakan sebuah kota yang terletak di wilayah Provinsi Sevilla, Andalusia, Spanyol Lihat juga Daftar munisipalitas di Seville Daftar munisipalitas di Spanyol lbsKota di Provinsi Sevilla Aguadulce Alanís Albaida del Aljarafe Alcalá de Guadaíra Alcalá del Río Alcolea del Río Algámitas Almadén de la Plata Almensilla Arahal Aznalcázar Aznalcóllar Badolatosa Benacazón Bollullos de la Mitación Bormujos Brenes Burguillos Camas Cant...

 

2017年堺市長選挙

2017年堺市長選挙 2013年 ← 2017年9月24日 → 2019年   候補者 竹山修身当選 永藤英機 政党 無所属 大阪維新の会 得票数 162,318 139,301 得票率 53.8% 46.2% 選挙前市長 竹山修身 無所属 選出市長 竹山修身 無所属 2017年堺市長選挙（2017ねんさかいしちょうせんきょ）とは、日本の地方自治体である大阪府堺市の市長を選出するために執行される選挙で、2017年9月24日に投開�...

真双子叶植物

真双子叶植物化石时期：早白垩纪 - 全新世 PreЄ Є O S D C P T J K Pg N 矢車菊 Centaurea cyanus 科学分类 界： 植物界 Plantae 演化支： 维管植物 Tracheophyta 演化支： 被子植物 Angiosperms 演化支： 核心被子植物 Mesangiospermae 演化支： 真双子叶植物 Eudicots 演化支 毛茛目 Ranunculales 山龙眼目 Proteales 黄杨目 Buxales 昆栏树目 Trochodendrales 核心真双子叶植物 Core eudicots 大叶草目 Gunnerales 虎耳草�...

 

Chuck Fairbanks

American football player and coach (1933–2013) Chuck FairbanksBiographical detailsBorn(1933-06-10)June 10, 1933Detroit, Michigan, U.S.DiedApril 2, 2013(2013-04-02) (aged 79)Scottsdale, Arizona, U.S.Playing career1952–1954Michigan State Coaching career (HC unless noted)1955–1957Ishpeming HS (MI)1958–1961Arizona State (assistant)1962–1965Houston (assistant)1966Oklahoma (DB)1967–1972Oklahoma1973–1978New England Patriots1979–1981Colorado1983New Jersey Generals Head coaching r...