palindrome-pairs_test.go

package problem0336

import (
	"fmt"
	"testing"

	"github.com/stretchr/testify/assert"
)

// tcs is testcase slice
var tcs = []struct {
	words []string
	ans   [][]int
}{

	{
		[]string{
			"beeeebcdeicajgjj",
			"ihjggahfgdecdgjdedi",
			"eaigjcciegijcgdcjea",
			"bdicecf",
			"feiihebjibiddcgcc",
			"fijj",
			"bbbgcihffajefeeadi",
			"jeca",
			"hhijbeccecaa",
			"aifjbigjfigdabacdh",
			"haj",
			"jehdgheabgbg",
			"caj",
			"giead",
			"fjjeehae",
			"bhbgaeabgbf",
			"deadjf",
			"daddab",
			"bdjhgchbi",
			"fb",
			"cedjdjdegchhjcdfeh",
			"jeahjejjib",
			"bgbfheeijfdbihcfb",
			"adijbibd",
			"deafbiibjbca",
			"bdhffghhgbidcciiiiaf",
			"aigahcacecbjfgiajeh",
			"jigifibdgcg",
			"ieajccfdeda",
			"hcacfaiceae",
			"g",
			"ehegg",
			"hbahheegccjacdf",
			"icea",
			"jdhajghidajgehf",
			"ahjcfhejgbgfacddgeg",
			"ffagecdjjidfbjeb",
			"gaaghabdd",
			"ehbjbcciei",
			"fgjdbcbabbfhh",
			"dcfbfc",
			"icca",
			"gahcjffhhdccgacdddi",
			"heegjjgddfde",
			"hejahhhfhjbdcb",
			"hecdffia",
			"fhidfgajhjfi",
			"bdibhdjaejefe",
			"adhecf",
			"jhieebddigahheicgc",
			"bghdjeceb",
			"fhhfjccdbbeaai",
			"dfhjeajbcgbgfjbiie",
			"gaaaiaahj",
			"gihgagfiabjaheaefjgg",
			"bbfgchfjfibgg",
			"giabcacjiaiigd",
			"cifeffjfjdcgeccddi",
			"cfajjie",
			"febcfjibeegehbggf",
			"jbbajgefgbiegeihgaf",
			"hjibifcbib",
			"hgbcifgjiiejghhabg",
			"dhaiigahggijacjb",
			"ajiejafg",
			"ddghi",
			"aifdhgbg",
			"idehafjcacafjhaa",
			"bedfchdcaicjfa",
			"bje",
			"eabbhhcbdj",
			"b",
			"cifc",
			"ajcabichajdijdhjah",
			"jjbj",
			"ejcfbadje",
			"ajefhghdgagdg",
			"cgjdfahec",
			"cajhbi",
			"ggahjiibacech",
			"jiii",
			"gbejbgjfggghgccic",
			"aedhbha",
			"cbgeajjacbffj",
			"gfaedaihaehchhfbca",
			"igegjjdfgcj",
			"cggdfbefidb",
			"aeggefjgidhcjai",
			"iccfgfjbifj",
			"babeeacadbgcejdgb",
			"hjfbiieg",
			"jgfjafegfcjabig",
			"cgghcbaigicccdadgj",
			"edhc",
			"bhfdggfeedjbcc",
			"idhfifjh",
			"dhg",
			"bigcjbedahicachdc",
			"hbhehd",
			"ddejegadb",
			"dcghcjidb",
			"h",
			"f",
			"bibfbgiigdjdhcicgfa",
			"j",
			"cfcbbcagdhficdfbgge",
			"diieibdchje",
			"iaideefbacd",
			"chbgg",
			"ejgfdifgdecidefadc",
			"hca",
			"ajhaacceddigfdaijhh",
			"jjcbbhh",
			"jcdejeiddeghibcdiahd",
			"cgbh",
			"jccgf",
			"eibbhcafih",
			"agfbaffjehf",
			"gciaddbdd",
			"caabfhbb",
			"dhiafhfghbbiaciebe",
			"hcbaijchdbibhijeij",
			"hje",
			"jgaagcgcbfhbhg",
			"baf",
			"gg",
			"fafifdcacdjajea",
			"babiaggad",
			"hidgc",
			"ihgfdeddjffcbfbg",
			"cga",
			"jjhcicf",
			"bgacedbcchbffb",
			"hbghiffibeeh",
			"ieeihfdihc",
			"dbdfhfcg",
			"gaf",
			"fibacfgcdhgci",
			"agdeibjediabfcgacaaf",
			"dhhddehiih",
			"ddaebjgifhjeide",
			"heefhfgdfa",
			"ji",
			"fdbajeehi",
			"cfjiab",
			"adbifjaddbidgec",
			"jcf",
			"hbebghj",
			"hbcebe",
			"gihjdadbcdjdeb",
			"cagicfjgibajj",
			"beibhadf",
			"ddahi",
			"afgcjdghiedaifbgj",
			"hbbchcbhd",
			"e",
			"cbcafdgg",
			"gdagdfdafhdbi",
			"haaeifhf",
			"jifegiibebddig",
			"iccaadccijjehhbej",
			"giabhggeba",
			"a",
			"afechgcgjh",
			"icaeaga",
			"dgchd",
			"ifafc",
			"bdecfaggfijdc",
			"cfihfjdagfbdjhfjjfgd",
			"fbgc",
			"fgefhdhhihhhcad",
			"gbdaifaedahbicejah",
			"ae",
			"ciafhbghigacjgbg",
			"fhjjcafh",
			"fifhibchebgibj",
			"dcfabcjbahbbgibifi",
			"hdjbjgcdhifji",
			"iij",
			"bbgahabheacdidfjgcdb",
			"hccdaigbeegcahgdhe",
			"hcffjjcfhfhdbhihjb",
			"abefdhjfj",
			"cdhba",
			"dcccigaff",
			"c",
			"ii",
			"jdhcgbhgjhdcge",
			"ddjh",
			"hehaihc",
			"ihj",
			"jiceb",
			"ddidajcbhe",
			"eidhcicecfhbjg",
			"ejiaiggbdjbffc",
			"ibcffeb",
			"bagchhdf",
			"bbaefcedhf",
			"bfeffgjcjcgfcjhj",
			"ciha",
			"ga",
			"aebcgjajdccbghh",
			"agjbijcefbbedaa",
			"hjchddgdffchbcbaaji",
			"geahiefhfh",
			"jfhjca",
			"jegcaci",
			"afhiiaedggj",
			"fce",
			"jjabde",
			"ejghfgbidafhgfddged",
			"eefjbdabfjdjjcfab",
			"ffcgebgejghcgga",
			"jj",
			"dhbihgahec",
			"ijadjcbdbdcaag",
			"ghi",
			"eddaeggiiahdegigd",
			"gef",
			"bgjhdhghgjjigb",
			"de",
			"cbhehdhcagiddh",
			"hahefidijehedd",
			"gjbcija",
			"fgfgedgijdhc",
			"jf",
			"ci",
			"egacd",
			"egdchfjaicga",
			"adcffgcbcfg",
			"gghcafhicegeffecej",
			"dibeeahcjhgd",
			"bddada",
			"jcc",
			"edbjfdaaadfh",
			"eeieahcfga",
			"ddjhaachfdgj",
			"adhhegabeid",
			"dbf",
			"gicdfaa",
			"faeb",
			"gfdfdbdeeehidjcddjf",
			"bcg",
			"jchahhacjhaicdh",
			"abjeeefbf",
			"idj",
			"habcgfbcfbafgbedeag",
			"dfjjcjihhjidhif",
			"giagidiaejhhbebgfiii",
			"dcjieibddijacedjjd",
			"djhbbeegjdbcdc",
			"hbjihacidcjf",
			"ebcjcbjggcejaedbjbgh",
			"ccjhffdgheii",
			"ebjjjidafeiiadagd",
			"ebgiccfjcdhij",
			"fahi",
			"gbfjedheihagdfjfiadj",
			"fbfcebefe",
			"cjed",
			"fciaffbfhheaajiee",
			"jhbeeccdbfffaefgbag",
			"ejdhijbfjedi",
			"abgcfhafdiihjgcjb",
			"gjdaedagb",
			"gaebghaficjij",
			"ggjcbb",
			"eeahgbehcdf",
			"bdh",
			"cfiecig",
			"ef",
			"jeagcjgj",
			"edjeeg",
			"ehdeahei",
			"jb",
			"dheaefcbiaaibihbi",
			"ceac",
			"fbbjifdbgeabahbeic",
			"ehceeieajcbcigdea",
			"ccia",
			"ejb",
			"jaa",
			"jdfccf",
			"cehdehada",
			"cajagdgbdfdief",
			"ecchaahfccahbfiiagh",
			"gfecfgiicf",
			"begeif",
			"ccdj",
			"chjece",
			"chjdcjhiaadiaja",
			"ehiffbeefbh",
			"ijeaaaab",
			"bbceg",
			"jhiij",
			"jbadgfdb",
			"cjfiffbgigjjehc",
			"deifejfji",
			"ccijhjdecbhbae",
			"jgdhhgjfdecicj",
			"edhjhecdehidecd",
			"faidghgaeiccgabaeeih",
			"ibabaafhegcbhadfgjfc",
			"hgcceegjceh",
			"cjjichhceebfhfe",
			"ihdibgjichedbejgjfd",
			"i",
			"ejjdiiahidjcde",
			"ghidg",
			"jaejg",
			"bdhbj",
			"dgcbagf",
			"ggjefhjaffeidecgi",
			"fhjf",
			"dahaedfcccdcddegfb",
			"dceagcfigijagaiagg",
			"ee",
			"bdfjhageebbdgjf",
			"idifga",
			"fdhcbjjdijcc",
			"hgii",
			"gcecbdjeebh",
			"gfjggaggaaeahdcg",
			"cjeaee",
			"deghch",
			"jd",
			"fbgbdaijfc",
			"jjbahggccfchgc",
			"idbigaa",
			"fh",
			"jhaffeiafcfic",
			"hjbajajbhhgbhh",
			"jcfffgi",
			"eid",
			"bdiddidbiehaicjjj",
			"cadefbfcdiia",
			"chbb",
			"jcdieaa",
			"chafeehdifjdhe",
			"dbjbdefdhh",
			"agiebcaafefbehfgfecf",
			"ajbcdccde",
			"bajddcfegdchbhaa",
			"gjdhffifjbghj",
			"fac",
			"ibhdghc",
			"ddcbheggh",
			"ja",
			"ehbecbic",
			"dhcahcdi",
			"eaicgfahhhcga",
			"ajgjadi",
			"cej",
			"ijf",
			"jgjiggibgegfcgdh",
			"dhbcgbdb",
			"idibfaecedbefh",
			"jhhad",
			"hbgfeb",
			"addjdgibc",
			"edfji",
			"jfhdih",
			"defdbchi",
			"hhcbbdbhfcjafaidi",
			"hjjfef",
			"afgiedffbebgdeceg",
			"caagacfafihjbc",
			"cbd",
			"hbechjjdhjcajhi",
			"ecdbhcfjiajjdi",
			"eafj",
			"eedgcddibhjicghhgi",
			"cebihhefjfaajgcbihh",
			"iad",
			"bhcjh",
			"bbfcfbhbjheffijffgci",
			"idfifbag",
			"ehhiifgefabajccif",
			"ccdhdgbg",
			"dbegdcffhej",
			"gbbhiddajaej",
			"dbcfgbaegdaefb",
			"jeafifjhgdggied",
			"dbfbgjg",
			"fhde",
			"dbbgjjihbb",
			"gejccfbehd",
			"dihae",
			"cbedgcefibh",
			"ibgdbbdeeafd",
			"gdacjhcae",
			"eig",
			"caiffaiecbjifbed",
			"bhbhicif",
			"jicegfihhfehdgefgbe",
			"gbceggcjifcgbe",
			"chaihfjha",
			"fabchhfgcbdeh",
			"haghigeccecfciachjd",
			"fejdbifdgihhgejejaij",
			"eahdcbjigibh",
			"bcaedbddccccfchaaa",
			"bbhghajdha",
			"icieaaihjfbjc",
			"haifhbehfeh",
			"fdbaiehdacbcg",
			"haiichhejicibifgch",
			"hcgjjdbfg",
			"gefhecjbid",
			"iijifbe",
			"fdccfgidfhfaefb",
			"ehhigje",
			"ehejhaadgjagajfgi",
			"dadebcejhjacj",
			"fgbhfgfdciebca",
			"iadfab",
			"ggihahf",
			"bfeg",
			"ddjfhaeefe",
			"eeacdagjacjif",
			"jadigc",
			"dgd",
			"ehhihj",
			"afagacheibifg",
			"cd",
			"eaaeddaijbjbcdhiaj",
			"ic",
			"cabfah",
			"aefbebcahfccgcc",
			"geafcjcccafjaafgb",
			"ecf",
			"bbegiajc",
			"dbeegbdbiadbiebbhijj",
			"ejjebcaec",
			"hhfabf",
			"fgiegjbfbajgagjedfd",
			"hgcje",
			"iiifeei",
			"iadhide",
			"jehbfiiebcebjgbfi",
			"bfgid",
			"ejjfijcbhhchc",
			"jedcjgfc",
			"bdecjaddjjjhddgejb",
			"bcedaeaicg",
			"beijbfihjiebicfbdah",
			"hbcifghfjdg",
			"bcf",
			"jjhbj",
			"fhdieehbfjhga",
			"efgbjgccg",
			"dhbaciegffcbgcdecfge",
			"cc",
			"ibibeaehdgf",
			"jecifgb",
			"hfcbjjddjig",
			"gcihafaajifgfjgee",
			"jbifgjecfaecf",
			"gfbjjhfj",
			"fgj",
			"eeddbihhhbcggb",
			"cdghjidd",
			"jdffiaccgdhebhfa",
			"fhjibdjjdhajacgdaa",
			"djefgjebeehbdcfgh",
			"geci",
			"fedcibeihbcdddg",
			"ba",
			"acjejdfcd",
			"adcggijbbdaaajcji",
			"bhgec",
			"ch",
			"gbggegj",
			"fdcj",
			"ghhjf",
			"geaeecc",
			"ebaehjfiegbhiiigj",
			"jbhhfhgcg",
			"djjhcebjhgjhddegjaf",
			"ddbbgbbgb",
			"dagejcifjiidhfj",
			"cigjjdba",
			"ddfjgecjbhibhdab",
			"igdh",
			"cjihcghd",
			"fgidhihgahiedcdhceec",
			"eccaeecchciijjhicc",
			"acjggfg",
			"gjfgjgdgcejegigbcj",
			"jdhchcdejbc",
			"hjchcjheeggebbgejb",
			"hgegdjedbeghj",
			"egigbbdg",
			"dddihccgiehijeee",
			"aebfhec",
			"ebeagii",
			"ejjajcaj",
			"chefcjciijgagbiddb",
			"jcha",
			"acbdhfigjbafj",
			"dcib",
			"hhhid",
			"cbj",
			"ibia",
			"fddh",
			"hjeeidijdifhceechj",
			"hieibajd",
			"fgeee",
			"jfbg",
			"egba",
			"dc",
			"ajjajgddeebgba",
			"hfhgjibig",
			"ehbdd",
			"hgdag",
			"ffiddacjcfcebfhafiad",
			"bah",
			"dibhacehhdahhfghi",
			"cfeagjcdhahgbhiefg",
			"fiddgc",
			"adbgdcifjabchhfj",
			"cfhcjidifgiebg",
			"jfbgbda",
			"jjfiijdb",
			"cdiegf",
			"agfhddhibhjchjahgfe",
			"eh",
			"gjhaadg",
			"bgj",
			"fifaiagcicgic",
			"hibdj",
			"ddaffibhjbjebjhed",
			"hfhjfh",
			"dejahcbheihaccfcaci",
			"hbd",
			"egfddiie",
			"fahgbhjbbegjcigf",
			"fhjdcacebdhfc",
			"fhihecei",
			"abeffcdga",
			"cdifdea",
			"jbde",
			"gbfcj",
			"ehgfiaebhbeafcadfiec",
			"fdcfac",
			"ebaajggaaff",
			"deifaeidijaif",
			"aafhehdihdiafcgf",
			"eihccaf",
			"bhhhchije",
			"iaheehiadeidie",
			"bgehefjheccgdjihde",
			"highgd",
			"jh",
			"hfbdfdcaf",
			"ecdddb",
			"gijbffg",
			"dbfbjefjdhbifch",
			"dcb",
			"adcceefaa",
			"difbcegagjad",
			"bicjchaigdidhbjbbc",
			"befdibhhgjfbjh",
			"jccebjagcbe",
			"bgggfhdfjhj",
			"figcbjdffe",
			"ggdfbgj",
			"efjaiicejebhaiij",
			"jbga",
			"ijedeijfbgcaicdchaa",
			"fc",
			"dffga",
			"jcadghifjeej",
			"bbeibajjghcjii",
			"hbiificbjggbdbcddgi",
			"cefhddgg",
			"jbifiecihibcajhhe",
			"befhgaja",
			"ddhjgj",
			"aifdedjiijjiifaefji",
			"jgigdbegdejed",
			"dbafbg",
			"bhiecchgeghgf",
			"bgejidbbcgjbbej",
			"gdjihbajbdjfbhhdgg",
			"cfjgc",
			"gcedgcfdcbhbaehbh",
			"fagbdceffcfeg",
			"dehdbdadeadheb",
			"jdjbcdaebefhfjefgib",
			"agghajfajcifiggcehbc",
			"figadcadgjbifacff",
			"fdhijdjei",
			"dbjehghfbfaba",
			"dddgihhaecfjia",
			"bjedbhdejbeccc",
			"gbaa",
			"jcbcjdicgdeafcjgfa",
			"jeieibahadejjia",
			"jejbegecjcghag",
			"degeeig",
			"idiefaiagbdccbeg",
			"bebbihjajiacc",
			"agcded",
			"jiajjghadiib",
			"ggiaicj",
			"gaa",
			"bjfegdebhdafcjc",
			"jedbe",
			"dcegghfah",
			"d",
			"cdcfhcejaidjhdihf",
			"jedahaebjgafjij",
			"eehhbfhcbheibeafbjhh",
			"iacbiidjjdafgdeebgeg",
			"ehg",
			"gce",
			"cibbdfjabajfhicjhc",
			"gabe",
			"bcahifdhefgcihfcj",
			"bachiajbbghf",
			"cbcggfjbddig",
			"aigjififbibbhee",
			"bhjichaeacebhde",
			"jhjjedbejhjef",
			"bdbgicjg",
			"hhbjeeig",
			"afcgd",
			"chb",
			"hidjidieebe",
			"fjeeaahabghbdijeehj",
			"ffehejehacheff",
			"bfhijbfhgeij",
			"fahffagajgifhegiahd",
			"daeagh",
			"bfhhcfi",
			"igaebicbbidc",
			"ahgaeadaeaeejhbbd",
			"hhfifc",
			"bba",
			"jhahbbgcahega",
			"cgbfjibbgejahhi",
			"fceidghhbc",
			"ddhbiijfagbijabhchg",
			"edfdgfhgedciijjb",
			"cggacbegcab",
			"cffddejagdedbjbhbehh",
			"iiabejchcegffe",
			"bfjdcjdiefifhdd",
			"idceadhahebjdaebaag",
			"ghfab",
			"gbbcabghjfjecb",
			"ca",
			"jacajeeee",
			"fiafccce",
			"addheieceacdbid",
			"gcie",
			"cegfjdjiifibbbfde",
			"bgjiefggbhajjjhdeeb",
			"cbhcdghcgjggbibefi",
			"jhaeggbeacc",
			"cdcebbcb",
			"eei",
			"fiehihb",
			"ddejbhahf",
			"ghacaijhbh",
			"dbjagbdjgadg",
			"aaecfdhfchicha",
			"bgfdjiddeaigeibie",
			"chaeffghac",
			"jeaiafidbebcdddchbi",
			"ceicfhhbceidigbijiga",
			"iebdcjcdgcchd",
			"feefcfjhegbibcef",
			"chjfbd",
			"bhehcgbaa",
			"dhaidbeigj",
			"ggfcihbjgaacg",
			"gbafcaccb",
			"icbgbdfccjiegfagehja",
			"deheh",
			"bjifj",
			"gig",
			"fiheejdgc",
			"afgcfbifgggiiac",
			"hjjgjiahec",
			"agebjdfbfbijdjciciac",
			"dbhgbeeabghfdaded",
			"cecccfedd",
			"idihib",
			"jjjefigiajaegd",
			"eieiabhefdg",
			"hhfdbgj",
			"hefhfafhegbddha",
			"abgbeifbcihjcjjf",
			"deh",
			"hf",
			"cacgihjgc",
			"cgechchgca",
			"fdghe",
			"aeae",
			"beefijjifh",
			"fhejjjgdjbfdfjbc",
			"jfhgccjgfeaejcdd",
			"cbehieicjgjb",
			"gabecadiafiidaedjhg",
			"bihahejcffh",
			"cdieiaicj",
			"aebbgdfefedbghcdjie",
			"hidhaaejcfddegdbj",
			"hhdfbhhgdib",
			"ajcagaadbhdjfjh",
			"jhcjhacaciahafgfbeae",
			"fbadf",
			"hdhghbhjg",
			"dicjdjhbh",
			"behjeedjfdchif",
			"jgbfd",
			"hhjge",
			"hjhjhhifihd",
			"gjgjceigcgabgeejb",
			"ieaeffdeba",
			"cchgjhe",
			"dafefccaagef",
			"bjfcddaaafifjbgg",
			"fhihc",
			"igghbbj",
			"aeadajbahefdaffgddfb",
			"gihfecbfbdih",
			"cififdedahjhie",
			"feeec",
			"bfe",
			"ijah",
			"babfbjjefeghdiif",
			"bj",
			"bfg",
			"fdbcfcicejedbf",
			"ggjgbajhdee",
			"ceaffjfffibaac",
			"bjacfedbcfc",
			"acbeeahbcaaa",
			"ehfhifbibbchgdcddeb",
			"hecdh",
			"bhi",
			"gehiiiifbedejjhhdjha",
			"cccifbgjigfhfaeef",
			"fciddhfiiheai",
			"daccaegdc",
			"jjciidaei",
			"abdhadcf",
			"affbdeehj",
			"adeigihacbace",
			"dcje",
			"edjg",
			"abfieiaifbehaegbdhj",
			"ceg",
			"efbgheebjih",
			"bi",
			"hbceaaciigghgeed",
			"fcjcjiaddafehcgdh",
			"cdhafhafcagecahh",
			"hdicbggdbhhaec",
			"jdffibg",
			"jfdgai",
			"jafddhhfecafccd",
			"ddecjfffdibhfbec",
			"aebdacjfbbabhd",
			"cejgjedbggc",
			"cfigijhghgjhjigaj",
			"didgicafefibfhia",
			"hfigi",
			"aeahfbhj",
			"ejfabcgidfebiejac",
			"cijadecfidbha",
			"ccefhhaddgefbec",
			"acaf",
			"iffafgffibbhjabifh",
			"cgaijjdiadjdijd",
			"jebhhifdcjdbgfaj",
			"ciiajeafhb",
			"ahgjhaih",
			"ffhjjjdf",
			"igbfdbcgdced",
			"hhi",
			"ajadfhdbfic",
			"dcicgbegafchdjbeaiac",
			"eeaieibbaahbj",
			"jaefgbgajceddada",
			"abdaeff",
			"baggdhigcidi",
			"digibh",
			"beeahagffig",
			"hecafdaibjac",
			"cbdiaaecebgddfebcgeg",
			"cjdid",
			"iag",
			"fdejghdbchcfhcc",
			"gieg",
			"hafhhjda",
			"cfiacbfbjaj",
			"acaaecbfa",
			"fghcdbhihfjgggbbe",
			"ddjiachf",
			"bceefdfch",
			"cibbcjfajbicjbeg",
			"eehbcbiebhdj",
			"ecdjefcagc",
			"cjfedhjgecdicejej",
			"eachghacfd",
			"bbeeabfgcj",
			"cjcibgaiji",
			"fijacjhbcce",
			"cdgjc",
			"echbchiiahbieeabeaj",
			"bhad",
			"heeegadbjcbbh",
			"biaga",
			"giijhchaidhajja",
			"aiccg",
			"jahigbhcijfceifab",
			"gbba",
			"chfjehffad",
			"acbfagcdiei",
			"dbjbhabehejgacigjief",
			"jdgbghhc",
			"iigffdaibedidbgai",
			"efhhbddeadaeedcbe",
			"hbaggcdhajeecf",
			"baachfdfihfhec",
			"hfhgcafh",
			"if",
			"ebddaigjbche",
			"ggcebefhcif",
			"cdhcfeghheadhb",
			"ibigdgehibfheafg",
			"ajgjdbediidiiedgbbj",
			"egcefhcaegcchab",
			"ffcccigbgddhiej",
			"jiihhffbdba",
			"higcb",
			"bdcj",
			"iibjghgddgibjdbhg",
			"jjbfgjbaegfeafdice",
			"eicfigbgcbfbh",
			"hbc",
			"ddai",
			"ebgedc",
			"dihhegaedie",
			"hhichheibgh",
			"ibfghigejcgccdgfhha",
			"hjaefhhgbeaabiiiia",
			"jcbgfbi",
			"iib",
			"dgifigccgeajacad",
			"ajadieihjddajf",
			"daaebahhceaaccjce",
			"ebcegebbaehihc",
			"dcdigbbfcjfjgejafih",
			"cahaeid",
			"jgadcfbiebh",
			"bjgehica",
			"jcdbecicddhgdcgah",
			"abebiggeegied",
			"iegidfdcaghbh",
			"abcgjhccecihjcehjbih",
			"ggbjjdbj",
			"ebd",
			"hb",
			"aegifehccjbfjdfgh",
			"fcgfhjef",
			"jcjecfjg",
			"cfjfejehj",
			"ebehfcefjagdehbgaf",
			"acbfcjbaacf",
			"ghfiiihbafg",
			"ggjfhjejjjebgi",
			"bedeg",
			"jhcgbdabcicjjcf",
			"jggejdjb",
			"gj",
			"jdj",
			"bd",
			"bihffeibbhhahdeh",
			"ciii",
			"ggggfigdahcbcggaea",
			"heibfaefccbcbjdjhf",
			"ej",
			"ijfia",
			"geaffgjgcdhfaigjhb",
			"jggbjcbjaigbhcajdgf",
			"ihjia",
			"cdafebccdfiejbihfa",
			"hcbfh",
			"cibeabfaceadjdcahcje",
			"cedhehfggahfdjafi",
			"idehcgghh",
			"ecbbahfbjga",
			"agegadhbcbggdjh",
			"icebg",
			"gdfhjdhgfi",
			"iibajaagg",
			"bc",
			"egdjeb",
			"ifg",
			"dbdihce",
			"djgcddgfhhjhfeficfb",
			"aifei",
			"adgbahccdhfggidff",
			"chaheaaibfjgaicjggi",
			"fabibje",
			"fgca",
			"dcfgejefjediehebfe",
			"jhcjjbehdaefehgfgddb",
			"gedfbgbddddgjihdai",
			"iheijfcccgjjic",
			"jhdcijachjdicida",
			"cdcgdjgbdgceagbgccij",
			"ijehdcaaii",
			"cedgjjcaga",
			"gbiahdcdbbgc",
			"dhdjjfgiic",
			"efajajhfdhggbdhd",
			"cibdgdchfiagcddihfe",
			"ffbbjbe",
			"afjib",
			"ddgicdhhcjebgijihfd",
			"ddchbjfed",
			"gjedbhgj",
			"jdb",
			"ijea",
			"hcjjhhecfa",
			"cghffiidjddgdjfig",
			"gjgebbhghbabfdfb",
			"gaeddgibiddfe",
			"hgihcbchageicggajg",
			"dadhjcfejbcefgdjgde",
			"agdbegjjdciicffc",
			"ggahfhcgdj",
			"ijaiiheecg",
			"eeficbjfbdjafbib",
			"bfagahdeddaeje",
			"fjagijihjaadj",
			"hecgddeahd",
			"jahccjdhgajhbcdhe",
			"bjae",
			"aggjagjdeejfbc",
			"fcefadj",
			"gaadg",
			"bcgdidjaiihabfg",
			"bfbjidcjbgaggd",
			"aggfjjgibd",
			"hfidbgiaiegcff",
			"dchegbggcgi",
			"idij",
			"gabbcdedcbieaefhcdbg",
			"iidbdidehdjj",
			"dbfdhebhiehh",
			"dgdbj",
			"fdfcjhjigcgbaibhcifi",
			"eadaafhfgdagajbe",
			"abagbjaaibb",
			"jhdjbfjfiijccdedd",
			"gbcd",
			"cedfiabchdijgbh",
			"ahjdbbja",
			"jiaag",
			"ghiifaiehaajc",
			"iejifjdchjci",
			"iacgi",
			"hdgf",
		},
		[][]int{
			[]int{5, 830},
			[]int{7, 352},
			[]int{347, 10},
			[]int{347, 12},
			[]int{19, 102},
			[]int{71, 19},
			[]int{125, 31},
			[]int{40, 610},
			[]int{886, 69},
			[]int{69, 274},
			[]int{69, 280},
			[]int{74, 104},
			[]int{274, 74},
			[]int{80, 104},
			[]int{80, 178},
			[]int{110, 471},
			[]int{886, 122},
			[]int{122, 553},
			[]int{125, 30},
			[]int{30, 125},
			[]int{142, 104},
			[]int{306, 142},
			[]int{570, 146},
			[]int{172, 162},
			[]int{155, 172},
			[]int{142, 178},
			[]int{178, 186},
			[]int{104, 178},
			[]int{186, 306},
			[]int{306, 186},
			[]int{553, 190},
			[]int{200, 30},
			[]int{162, 200},
			[]int{208, 430},
			[]int{213, 104},
			[]int{104, 213},
			[]int{220, 610},
			[]int{155, 220},
			[]int{225, 104},
			[]int{102, 225},
			[]int{226, 185},
			[]int{306, 226},
			[]int{226, 426},
			[]int{233, 104},
			[]int{452, 233},
			[]int{19, 238},
			[]int{238, 881},
			[]int{325, 245},
			[]int{270, 155},
			[]int{102, 270},
			[]int{274, 104},
			[]int{71, 274},
			[]int{274, 734},
			[]int{734, 280},
			[]int{280, 69},
			[]int{281, 104},
			[]int{325, 288},
			[]int{316, 155},
			[]int{155, 316},
			[]int{325, 104},
			[]int{610, 325},
			[]int{329, 102},
			[]int{101, 329},
			[]int{329, 696},
			[]int{652, 344},
			[]int{347, 104},
			[]int{162, 347},
			[]int{353, 142},
			[]int{367, 901},
			[]int{218, 417},
			[]int{424, 185},
			[]int{610, 424},
			[]int{424, 510},
			[]int{426, 306},
			[]int{185, 426},
			[]int{426, 226},
			[]int{570, 430},
			[]int{430, 208},
			[]int{570, 447},
			[]int{452, 185},
			[]int{185, 452},
			[]int{465, 755},
			[]int{467, 71},
			[]int{162, 467},
			[]int{471, 185},
			[]int{101, 471},
			[]int{274, 502},
			[]int{502, 901},
			[]int{162, 503},
			[]int{510, 610},
			[]int{185, 510},
			[]int{510, 424},
			[]int{526, 155},
			[]int{101, 526},
			[]int{553, 104},
			[]int{101, 553},
			[]int{901, 558},
			[]int{558, 424},
			[]int{717, 566},
			[]int{570, 102},
			[]int{185, 570},
			[]int{603, 130},
			[]int{606, 30},
			[]int{162, 639},
			[]int{652, 185},
			[]int{162, 652},
			[]int{662, 316},
			[]int{306, 662},
			[]int{696, 101},
			[]int{102, 696},
			[]int{696, 329},
			[]int{700, 162},
			[]int{155, 700},
			[]int{270, 731},
			[]int{731, 19},
			[]int{10, 732},
			[]int{734, 71},
			[]int{104, 734},
			[]int{734, 274},
			[]int{735, 19},
			[]int{743, 867},
			[]int{757, 71},
			[]int{306, 757},
			[]int{770, 329},
			[]int{344, 775},
			[]int{102, 775},
			[]int{306, 783},
			[]int{200, 795},
			[]int{797, 391},
			[]int{818, 279},
			[]int{830, 306},
			[]int{102, 830},
			[]int{373, 845},
			[]int{757, 852},
			[]int{852, 186},
			[]int{71, 852},
			[]int{867, 101},
			[]int{71, 867},
			[]int{879, 30},
			[]int{104, 879},
			[]int{325, 880},
			[]int{881, 71},
			[]int{610, 881},
			[]int{883, 185},
			[]int{883, 426},
			[]int{886, 155},
			[]int{104, 886},
			[]int{901, 71},
			[]int{185, 901},
			[]int{881, 928},
			[]int{104, 953},
			[]int{274, 957},
			[]int{558, 962},
		},
	},

	{
		[]string{
			"bat",
		},
		[][]int{},
	},

	{
		[]string{
			"bat",
			"tab",
			"cat",
		},
		[][]int{
			[]int{0, 1},
			[]int{1, 0},
		},
	},

	{
		[]string{
			"abcd",
			"dcba",
			"lls",
			"s",
			"sssll",
		},
		[][]int{
			[]int{0, 1},
			[]int{1, 0},
			[]int{3, 2},
			[]int{2, 4},
		},
	},

	// 可以有多个 testcase
}

func Test_palindromePairs(t *testing.T) {
	ast := assert.New(t)

	for _, tc := range tcs {
		fmt.Printf("~~%v~~\n", tc)
		ast.Equal(tc.ans, palindromePairs(tc.words), "输入:%v", tc)
	}
}

func Benchmark_palindromePairs(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, tc := range tcs {
			palindromePairs(tc.words)
		}
	}
}