ImageRepeat
SRM 256 · 2005-08-02 · by lars2520
SRM 256 · 2005-08-02 · by lars2520 · Search
Problem Statement
Problem Statement
You will be given two grids of pixels, where each pixel has an ASCII value between 32 and 126, inclusive. Your task is to find the size of the largest square subimage that occurs in both grids. A square subimage of size k is a square region of the input covering pixels from (i,j) to (i+k-1,j+k-1). A square subimage of size k exists in both grids if there exists some (i',j') such that the pixel at (i+x,j+y) of imageA has the same value as the pixel at (i'+x,j'+y) of imageB from all non-negative x and y less than k.
Constraints
- imageA and imageB will each contain between 1 and 50 elements, inclusive.
- Each element of imageA will contain the same number of characters.
- Each element of imageB will contain the same number of characters.
- Each element of imageA and imageB will contain between 1 and 50 characters, inclusive.
- Each character in imageA and imageB will have ASCII value between 32 and 126, inclusive.
Examples
0)
{"ABC",
"BCD",
"CDE"}
{"ABC",
"BCD",
"CDE"}
Returns: 3
The images are the same, so there is a square of size 3 that is repeated.
1)
{"ABC",
"BCD",
"CDE"}
{"ABCXX",
"BCDXX",
"CDFXX"}
Returns: 2
2)
{"CEBACBABBDCCCACCDCBD",
"EBAEBCBEBBCCEABEECED",
"CEAEAEEEADBDEDABDCCB",
"EDCEACDABDBCBEECACBD",
"CDCBCBCCBCCCADDCAEDC",
"ACCBAABABDABEDEACABC",
"DCCADCACAEBCBCCCEEEB",
"ACDABCCCBAABBAEBCBDA",
"BACEEADBBDBAABCCBDBE",
"AACACCCEEEBEBDCEABAD",
"CABACEAAEDDEDDAAEDCC",
"DDCEAEEBBDBEDBACCCAE",
"CDABEEEDBDEBCEBECEAB",
"CDBBDDCDCEDBDEEBCEDD",
"DBDDBCBAEBBCDAECEBDA",
"DBBBECAECACADAACACEA",
"BDADACDEECCBABADEDDC",
"AEBCABCCABCBBCBABBEC",
"DDCEAEDEDBCBBABBCCBC",
"DBBEEAEDDCABCEAACBEC"}
{"CBEEADAEDCDDCEBEEADC",
"BDBDABCBBDBACEACDACA",
"ABAABDAADBCECDCEAACE",
"DDBAAAACAAAAECBDAEDA",
"EEAAABABCDABAEBEABAE",
"CECADCCEABEBEDCAEABA",
"DDECACDEECBBCBDDCDAE",
"CAEAAEDBADEECAACDAAA",
"EAECECBCDAAEBDECBBAB",
"CBCDADDDBACEDBBABACC",
"DCAEAADBEBEACDEDCCEC",
"ACACCBEACEBBBBEEACEC",
"DEDEBEEADCAECEBDDBEA",
"ACACACEADCACEAACEDAD",
"DCACBEEBCBDEDADACEEC",
"EDDEDCDCCEDBCCDCABDC",
"CABECBAEDCACABDDDADD",
"CAEDAABCCCCDEDAEABDE",
"CCDACADABADECDEACCED",
"BEDADAADACAABAAEBADB"}
Returns: 3
3)
{"EHAFFGCFBCHBFACBCBEDDCHCDAFBFHAFBEEFEGBFFFDCBBECEG","GFDFEGDEHGAFABCCEDDCEDCGCDCEEFBEGCFAAFGHBHECGDFHGE","BHGEDDHADCECDDHACFGBEDABBBDCCDDCDFBGGBABGEBFHECGEC","HDAHEFCBBAECEHDHEDCHBDBFHGAEGEDBFDAGDDCEHGBFHBCBGH","AFECBHCFCGGDAHFFDDFFDGFEBDCDBEAHBCBEGHCDDHFFGCHGCH","EHBFBFFCGEFGEBDBFEECDABEBDEDADCAFDGDEBGAHHGABHGHFD","DCHBAECGDCFBGGBCHDAGCFAAFBBDEAEBHGGEDDCDHBEDHEDEFG","GBFFDGEFGCGEDCBAAGBFDBFDDBEAGDGCBFDCHHBDCGGDCBAGAB","CAACCGFFBEHCFCCDAHCEBDEBFBBDAEGHBHCGCFBFCAEHFACHAA","DDGCABAFEDCABDAEFEHFGAHGEEFCBBEEHBECEEFEBEECCAEDBF","HAFEACDFABEAGCGADFCAEDBCBGFAHBFEFFCGDCGECHBHCDDCHB","CFEGGFACEGFFCCCAAADAGCCFCCDEHAGFHACAFCGDEAAADDGBFD","DAFGEACHGABCCEAFABDEGBCAFCCFEABDHBFCGAGGGCFBHHBBGA","AGDGABBFFHEGFDABFBFCEBGGHAFDBGCDFAFBFDAADECEDCAFAF","GAHEGFFBDDCHCGCFHAHAFHFAAHDCADBABDBBEBAADAHCECGDCA","CCBGBDHCDAEEFDDFCFFEBEFBDFHACDDDHBDGHFDGCDFBFGDGAB","CAFHFDCGGHDAEFCEHCFAHBHDCHFEFCFFHEAEEEECEEGEDAGADE","GBCFCFBHDCACAGEDCCAFGGEGCBEECDBFCCEHHHDFBDFHEBBGFG","FABFCCHEDBEDHBEHFAFGEFECGHCGFCAEEGHCGFEHHCFDDCDDBB","AEGGDEGHHFDDCCBFFHHGGAFAGBDFFDBGBHCECDADCHCACAEHAA","AECGEEGFCEDECDDBEFACCCCEEEFCCHHDADFFHHGCGHCBDGBFAC","BHFBFCEGCEECEFAHGCBDCECCADDEAAEEDDFHCHAGHHEFBHFEBA","DDFGEGFABEFCEHGBHBDGHHBBABEECGHEGEGDBGGDGFDHDBDGCC","GEHFEHHCEEACAHHAAEGDFCDFCHGBGFBDFHBBHGGHHGBFCHFAAE","ADFHHHDDBGAEDGADFFHAAGCEHDBHAGDDBGGABBAFFCDBEEGFCG","FHEGFAAAAFGDGHDEDDBBGBFHAEADABGDGHGCBGEFBFAHFGGEBE","CEBGHEAFBFBHCBAGCFDDEABCGEBBCEHCEBGFAFDDCGHDABHAHF","BBEBGAHCGDHHCEEGEHCFHHAGBFFCFHFHEFFEDFHCHFCBCCCCEE","GGACCGGBCHFEEGHEFCABHDEHAFCCGEFDFBCHDEEBBGGCHACCEH","AGBHHHGDFCCAEADACCCCCHGDAHBCCGHAAADDADEACFADAHDAHH","EEDFCGEFHDHFEBDFDEAADEAFACGAHHFFEEGDBFBFEGFGHEEDFF","DDDEABEEAFDAFCEEEEDAHFFBFEABHABGECCCDHGADDCDGGBGHF","EBBHDGDAAGFBCCEDBDEDFFCFFGGGHAFCBBHGBCGDEHEEBCFBGE","BABFBHBFACGFDHCBFAGAFFBCCFEAFFGHHEFCAHGDDDBFEEAFBB","HAGHEEAEHGCGFEDBCBGGHEHCFFCGEBFFFHFDGBBGBCHFGHCAHF","HBEBBBCBCGBGAGCHDDGFGCGFHHCGDHCABAACECCABGAABDGGAF","AGHDBHGABDCBEEDHDGHBBBBBCHBCBBFHDFHGFGHBHCCCFBBFGB","DGHCEFFEFADDDHHEBHDBFGHFDABEEDDCECDFHAEHAHEFEAEEEA","GAEHEHACFEGGBECHEBCAABHCBEBDCFHHHDAAAHBBGEBBFBEDCE","AGFDFDDDCHFAGBEHGADFAAHEHDCEECABFACDHFGFEFADHDBEEA","GDGACFFHBDDCFBDAGBCCFHEDFHDFFFBABHEBHGCDBBFCEDBHDG","AEECCCHCDDHECHGBHFGFDHDCDCCCADBEAACHGAAHAFGBFEDDBE","GDAEFBCDDGHACDAGAFAEHHAEEFCBHHGEBEFFEAFHGDCDEEHCGE","GDCHHFBDDAFABFECCCHGHHFDFCADBBDGADDGAHDEFEGADDGAFB","HGCHHEEBDFACAFBDHHGHBGABHEHDBDACEBHFBCHEAHCBHGFEHB","FAGFACCHEFEHBEHBHCEEAAHHADEBCGCBEDAGCFGCFGACADAEFF","GHDEDEAAHFCGDBBBDHCFFAFFBEDFECFCDCHCFCBBFGFBBEDBDC","GEEFEGAAHAHGFABADFHHHEECDCBGDACBBGDBBFGEEDCBBBGCHF","GGCHGCADCBFAFGABDHCDFBFBAEEFHFDHHCHDADAHEGBCDFGGFB","FBAFGDECCHCGHEGGCCCEGEDBAHHCEGBDEFAEFFHFAHBEEECBFC"}
{"AEFDFBFFGBAHDCECDDACEEGFCDEFGAGCGHEECCGAEFHFGCADCG","GGDEDFCCAHCDDHEFGBEBBCCBBADAABHAFHCHDGBAHCAGGEFFEC","CDABEHFHDCGAGFDHGBFFGECHFDBADBBCGHCEBCAFAFFBDCAFDE","EGCBEBAFCHDCCAFEECFFBFEFCAAGEGDDHGBEAHAACBCGAAFHFA","GCDCGFBBGCDFFFGFAEBCFBBHCEFEEFDGFABGGDFAEDAHABEGAF","CDCFDCDAFHFBFBAFBHFGADCFGDDGCCCFHCHCFADFDDHDBHCEEE","HCHDHGDFHAAFGEFFEGGGCHBCFBCDDFDGCDCFACBFACCDEHDFHE","ABBGHADBEBECFGEAHDBCGCGAHHDHBADBFEBAAGHFDCBHFDHFAB","AHFGCFHDDFFBHCFBEDHCFCCECDBCFHHFCACHDGCHHGHECBCGGG","CHADFDBCFGFBDDDDGFBHBBEBBGDGHAEFBCFDBGEEEGGAADCEGB","FEHHEEFBECHAFGFFFCDAAEACBHHFGHBEBGEBBBDGDBEADAHFDD","EECEBABADFCAAHHHBBEBABGHECDHHDAFDHFDHHEDABEGDDAGGH","GACEEEAGGAEGDHGHHEFEFBABGBDEEBBFFCDECGDHCAAHHDGHBF","AEABHEHACHGCFCABGFFGHFFGGDBCHACDBGGACECFDCFCGFGHAA","EECAADGHAFDFBFHFEHBGCFCHBDBHHDHGCBDAEBGDFHCECDEDHC","EBCFDBFDDACDFABDGHCEEECCEFHAFDHAEAAAFEGDCGDAFEAEGF","CBABHHEDAECDEGABEEGDDEDGAFEFHGACEBEGDBFCDCCBCFHDAB","CBDBEGBHGBDABEGEFFBEHFFAFEBFBEAFDAEEBDGCBAHDCEGCFE","CHABGGCFDDGEHBHCDGEFBDEFEGAAGCBACEAEFFGEEAEHHFHABG","DABDHEFGGAEDCBAAGGDBCHEAEGGCBGGEHACDGFGEGGGBFEEFAB","FGABFDAHFDBBBFCEECCGCEAGCBHCHGCAHHHEBAHHFEHGFBCDCC","EHEADEDGFHEBEDCAGHBACEBFHFDGFGBFBDBEBAHBFCACADDDFG","BDHABCAFBCHBBBAEGGFBDAABBFGEGDAFHAGDDEGGBDEFBBBCAG","GEBBHAFGBEHCFAACADBGBFDACHFADDDADAACADCHHFBDDFBBAG","DFHGBCGEDGFDEFFECBEDADHBFECGBBEEADCFGEDAEDABGDHEGB","CBAEHEDHAHHAHGGBAHDBDGCFHBBFDAHGEEBBAFCDBGHEGFACAA","EBHBAAHHBHCBCGFECHGHHDHCAEHDFFEAHFEFFFHDDCBEFAGCHF","ACBBGGEGDAFCBDAEFEEDBHDAACDFCEEDFDBBEHGBACHBDHDFEA","EHFHHGHDEDCFCDDECECHHDEDFDADAGDBGEGEDACHEDEBHFGEBB","CFCBCGHAEAEAAHCECFCGEGHABHHCACABHFGECFAGFFDDDDFGHF","FDAGFCGHDBEDCGEFFFDEEBACCHDDCDEDEGBCAGGCGCGCHEBDCE","FAGEGHFAFGAHCDACHFFHAGAGBHHFBFBEBAHBCAGAHCGCGEABFC","CHGDFEGDABFFCBCFGBDAECEGDECBHAEFHAEGHFGECFFGECFGAA","HCECHBEBHHGEFBBEEEFEEEGGHEFFGBGFACHFFDBCEGBEGDGDEB","FFAHDFCGAFCFGEHGFAHEDHHCGCFHABDBECCAGBCCADFGDACGGA","AFBGEECDFBFADEHFHFEBEHBHFFACDCEEABFDGDDGCEHCGHBHGC","BFHCGACEBCBCEHHAHEGGADEFCHFAGCGCCBHGEAEDDDBGADGAGH","CFADECDAFBCDBAADCHHDEDHGDECEEAHCCHDEEECDADCEDBGCBG","BDEDDGEBHACEEEBCFGAAHCECDAFCACGBGBADDGAHCEDACCCAHG","EHGDCGDGAHEFADBGCFGGDBDBHAAEGBCFBBEHBGAADDEEBCFFCD","DADFFHDBDCAEDCBDEFHDCADFEDADBBAEAEHGDFEBBGHEABAHAH","GFHEFFAGEECEECBFFBDEAEHECEHDHDGBCHDGCACCDACGFDCEFC","HBAGHDADHDCCADCDEHEBGCGCFDBEFCBCBBAAGGCFHACCBFEEFC","ABGAFBHAFABGEABGGGGHFCDDBDAGGEGDCAGEAFHGCHHBCDHCBH","HHFHGEGGDAEGBEAGDABBFFEFBGCECGFGHGHBHDEGCHGDDAHFFB","EGDFAHDHECBECGEGEAEEAFAEHCHEDGEHCADAHFCFEDCHBDCBEH","ABFAHCGGGDDFEDBAAGFBFEAFDBCCGCEDGBGAHGHEGDACABGCDF","EDGECGCHGFHHBCFEBCHFGGFBGEABBHBAHDAHGACGEGBAABBGHD","EHEBCBBHGBAHEHABADACDAAGGEHBFDCEEACGCGADEABDCAAEBC","EEDFBAEGDEAHHCFFDDGFDHHBFECCBFBAHDCGGHFHCEABBBHFDD"}
Returns: 2
4)
{"AAABABABBAABBAAABAABAABAABAABABBAABAABBABAAAAABABA","BAAABABBABBBBABBBBAAAABBBBABBBBBAABABAAAAABBABBBBA","AAAABABBAABABBBABBBBBABBBBABABBBBBAABBBAABBABBABAB","ABBBBABBABBBBABBBBBBAABABAAAAABAABABBBAAAABABAABAB","BABABABBBABAAABBAABAAABAABBBBBABBAAABAABBABAABBBAA","ABAAAABAABBABAABABAABAABBBAAAABABBBBBABABABBAAAABA","BABBABBABABABABAABABBBAABBABBBBABAABABBBBAAABBAAAA","BBBBBBAAABBBAAAAABABBBBBBBBABABAAABBABBBBBBABBBBBB","ABBAAABBAABAABABBBBBBBBAABBABAAAAABAABBAAAAAABABAA","BBBABABAAABABBAABABABAAAABBAABBBBABBBAABBBABAAAABA","BBBAABBABBBBABAABBABBBBBBAABABABABABBABBBBABBBAABA","ABAAAABBAABAABBBBABBBBABABBBAABBAAAAABABBAAAAAAABB","BAABABBBBBBBABABAAABBBBBBABABAABAABABBBBABABAAAABA","AAAAABBBBBBAABBBABBAABABAABBAAAABBAABBBABAABABBAAB","ABAAABBBABBAABAAABAAAAABBAABBBABAABABBBBBBBBBBBBBA","ABABBBAAAABABABBBABAABBABBBBBBAAAAABBABAABBAAAABBA","BBBAAAABBABBBABABAAABBBBABAAAABBAABBAAABBAABBAABAA","AAAABBBAAABAABABAABAAABBBBABBAABAAAABBBAABABABAABA","ABABAABAABBABAABBAABBBBAABBBBBABBABBBBBAAAAAAABABA","ABBBAAAAABBBBBBABAABBAAAABAABBBAABBAAAABAABBBBAABA","BBABAAAAAABBABBBAABBAAAAAABAAABBBABABAABBABBBABAAB","AABBBABBBBABAABBBAABABBBABBBBBBBABBBAAAABAABABBAAB","BABBABBABAAAAABAAABBAABBABABBBAAABBABAABBAAAAABAAA","BBBBAABBABABABBAAABBAABABBBABBABBABBAAAAABABBAABAB","BAAAAAABAAAAABBAAAAABBAABABAAAAAAABBAABBAABBAABABA","BAAAAAAABBBAABBAABBAAABABBAAABAAAAABBBBABAAABBABAA","BAAAABABABABBABABBBAABBBBAABABAAAAABBBBBABABBAAABA","AABBBBBBBAAABAABBBAABAAABABABBBAAAAAAAABABBABBABAB","ABABAAAABAABBAAAAABABBAABAAABABABABAABAAABAAABBABB","AAAABBBBBBAAAABBABBAABABAAABBABBABAAABABBABBABBBAB","BAABBAABBABBABABBBABBBBABBABBABAAABAAAABABAABAAAAA","ABBAABABBAAABABBAABBBABBABABAAABBBBAAABBBAABBBBABA","BBAABBBAABAABAAAABABAABABBABBBABABAAAABAABABAABBAB","ABBABABAAAAABBABBAAABBABBBBBABBBBBAABABBBAAABBBBBA","AABABBAAABBBBABBBAAAABABBBBBAAAABAAABBAABABBABBABB","BAAABAAABAABAAABAAABAABBBAABBABBBBBBBAABBBBBAAAAAA","BABAABAABAAABBBABBABBAABAABABBBABABAABAABAAAABAAAB","AABAABBBBAAABAABBABAABBABBBBABAABBAABBBBABBBBBBBAB","ABABABBAABABAAABBAAABABBBAABAAABABBBABAAABBAAABAAA","BBABABAAAAAAAAAABABABABBBABBBAABBBBABABAAAAABABBBA","ABAABAAAAABAAABBAAAABAAAABBBABBAABBBBABABABABBBBAA","AABABBABBABAABAABBBBBABBABBBBBABBABAABBBBAAABABBBB","BABBBBBAABBBBBAABAABAAABBAABABBABBABABABAABAAABABB","AAAABAABBABAABBBBBBBBAAABBABBAABABABAAABABAAABBABA","AAABBABBAABABBBBBABBABBBBABBBABBABAABAAABBABBABABB","BAAAABABBBAAAAAAAAABBBBABAABAAABBAABABBABBBABBBABA","ABBBBAABBABABBBBBBBBABBBAAAAABBABAAAAABBAAAAABBBAA","BABABABBAABBBABBAABABBAABBAABAABABAAAABBBBBABBBBBA","BBBAAAAABBAABBABAABAAAAAAAABABAAAAAAAAAABBAAAABAAA","ABBBBBBBBBBBAAAABBBABAABAAABBBABBBABABBABABAAABBBB"}
{"BABBABBAAAABAABAAAABAABABABBABBBBBBABABBABBABBBABB","ABABAABAAABAABABABBBBBBAABBBBBBABAABBAABBBBBBBABAB","BBBBABBBAAAABBABABBBABAABBAAAABAABBAAAABAABBAABBAA","BAABAABABBBAAABABAABABBBAABBAABBABABBAAAAABABABAAB","BBBABBBABAAAABBAABABBBBAAABBBAAAAAABBBAAABABABBAAA","ABAAABBBAABBBBAAAABAABBBABBBBBBBBBBBBBBAABABBBABAB","BABBAAAABAAABBBAABABBBBBBAAAAAAABBBABBBABAABBBBABA","BABBABBAAAABABBBABBBBAAABAAAABAABABBBBBABABBAAABAA","AABAABABBBAAABBBAABAAABAAAAAABBBBAABBAABBBBABABBBB","AAABABAABABABAAABAAABAAABBBBBAABBAAAABBAABABAABAAA","BBBAAAABAABBAAAABBABABBBABABABBBBAABBBBAABBABAABBA","AAAABBBABBBBABBABABBBABABBAAABBABBBABABBABAABBABBA","AABABABABBBAABBBAABABAAAAABABAABBAAABABABBBBBBABBA","ABBABBBBAABBBBABBBBAABAAABBAAABAAABBBBAABBBAAAAAAB","AAABBAAABBAABBBAABABBBBAAAAAAABABABBBBABAAABBABBBA","ABBBBAABAAAABAAABBBABABAABAABBBAAAABBBAABBBAABBBBB","BBABBAAABBABBAAABBBBBBABABBBABBABBBABBBAAAAABAABAA","BAAABBABABABAAAABAABBAABBAABBABAAABBBAABBABAAAABAA","ABBABAABAAAABABBABBABBBABBBBBABBBAAABABBBBABABBBAA","ABBBAABABBBABBBAABAABAAAAABABABAAAABBABABAABBBABBA","AABAAABBAAAAABBBBAAAAABBBBBABAABAAABBBBAAAABAABBBB","AABBBAABAABBABAABABBABBABBBABAAAAABAABBABAABABAABA","AAABAAABAAABAAABABBBBBAAAABBBABBABABBBBBAABBABBABB","BABAAAABBBAAABBBABABBAABABABAABAAAAABABBBABABAAABB","AABBBAABBAAAAABAAABBBABBABAAABABAABAABBABBBBABBBBA","BBBBBABAAAAAAAABABBBBBBABBABBAAABBABABBBAAABABBBAB","BBABBBBBAAABBAAABBBBBAAABBBAAABAAAAABABBAABAABAABB","BBABAABAAAAAAAABBAAABAABABBABABABABABBBAABAAABAAAB","ABABBABBBBAAABBABBBAABABAABBAABBABAABBAAAABAAAABBA","ABABBBAAAABBBBAAABBABABAAABBAAABAAABABBBBABBBBABBB","BABBBABABABBBABBBAABABBBABAAAABBBBABBBAABBABBBAABA","AAABAABBAAAABAAABAAABBAAAABAABAABAABBAABBAAAAABBBA","BAAABABABBAABABBBABBBBABBAABABABAAABAAAAAABBBBAAAA","BABABBBABBBBABABBBABBBBAABABBABABBAAAABABBBBAAABAB","AABABBAABAAAAABBBBABBBBBBBBBBBBAABBBBABBBABBBABAAA","BABAAAAABBAABBABBBBABAAAAABABABBAAABBABBABBBAAABAA","ABABAAABABAABABBBBABABABBAABBAABBBAABBBAABAABABBBB","ABAABABBAABBBBAAAAAAABAABBABAABABBAAABBAAAABABBAAA","AABBABAAAAABAABAAABBBABBABBBAABAABBBBBBAAABBBABAAA","AAAABAABBBBBABBAABBBABAAABABAABBAAABABBBABABAABABA","ABBABBAAABAAAABAAAABAAABABABBBABAAABBABABAAABBBBAA","AAABAABABABBBAAAABBBBBBAAABAABBABABAAABBBBBBBABBBB","BABBABBAABBBBBBBBABAAABBBBBBBBABBABABAABBABBBBABBB","BABBABBAABABBBABABBBBABBABAABBBAABAAABBBABBAAABBBB","BBBAAABBABBBBBABBBAAAABBBBAAABABAABBBABBABABBBAAAA","ABAABBBABBAAAAAABBABBAABBBAABAAABABAABABAABAABBBBA","BBAAAAABBAAAAABBAAAABAAABABAAAABBBAABAABBAAABABBBB","BBBAAABBBAABBBABABABBBABABBBAABAABABBBAABAABAABBAA","BBABABAABBABBAABBAAAAAABABABABAABBBBBAAABBBABABABA","BABBBAABABAAABBBBABBABBAAABABABABBAAABAAABABABBBAB"}
Returns: 4
Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ImageRepeat with a public method int largestSize(vector<string> imageA, vector<string> imageB) · 117 test cases · 2 s / 256 MB per case