Coding Solution for MAR points
Name : ALANKRITI MALLICK Dept : CSE Sec : B Roll : 13000119101
Question : Write the code for finding all common substrings between two strings of size m and n in O(mn) preferably in one pass The function should also return an array for matched indexes as: The array contains 4 elements as i4 = start idx from X i4+1 = end idx from X + 1 i4+2 = start idx from Y i4+3= end idx from Y + 1 for ith substring, and also the number of matched substrings This should in turn be used to print all substrings that is greater than or equal to filterSize.
OUTPUT:
The input strings are: the deadly war continued without any seen benifit only the dead has seen the end of war - Plato
All the matches are: o n l y t h e d e a d h a s s e e n t h e e n d o f w a r - P l a t o t . . . . . X . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . X . h . . . . . . X . . . . . . . X . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . e . . . . . . . X . . X . . . . . . . . X X . . . . X . X . . . . . . . . . . . . . . . . . . . . . X . . . X . . . . X . . . X . . . . X . . . X . . . X . . X . . . X . X . . . . . d . . . . . . . . . X . . X . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . e . . . . . . . X . . X . . . . . . . . X X . . . . X . X . . . . . . . . . . . . . . . . . a . . . . . . . . . . . X . . . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . d . . . . . . . . . X . . X . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . l . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . y . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . X . . . . X . . . X . . . . X . . . X . . . X . . X . . . X . X . . . . . w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . a . . . . . . . . . . . X . . . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . X . . . X . . . . X . . . X . . . . X . . . X . . . X . . X . . . X . X . . . . . c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . X n . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . . . . . . . . . . . . . . . t . . . . . X . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . X . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . n . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . . . . . . . . . . . . . . . u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e . . . . . . . X . . X . . . . . . . . X X . . . . X . X . . . . . . . . . . . . . . . . . d . . . . . . . . . X . . X . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . X . . . X . . . . X . . . X . . . . X . . . X . . . X . . X . . . X . X . . . . . w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t . . . . . X . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . X . h . . . . . . X . . . . . . . X . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . o X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . X u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t . . . . . X . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . X . . . . . X . . . X . . . . X . . . X . . . . X . . . X . . . X . . X . . . X . X . . . . . a . . . . . . . . . . . X . . . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . n . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . . . . . . . . . . . . . . . y . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . X . . . . X . . . X . . . . X . . . X . . . X . . X . . . X . X . . . . . s . . . . . . . . . . . . . . . . X . X . . . . . . . . . . . . . . . . . . . . . . . . . . e . . . . . . . X . . X . . . . . . . . X X . . . . X . X . . . . . . . . . . . . . . . . . e . . . . . . . X . . X . . . . . . . . X X . . . . X . X . . . . . . . . . . . . . . . . . n . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . . . . . . . . . . . . . . . . . . . X . . . X . . . . X . . . X . . . . X . . . X . . . X . . X . . . X . X . . . . . b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e . . . . . . . X . . X . . . . . . . . X X . . . . X . X . . . . . . . . . . . . . . . . . n . X . . . . . . . . . . . . . . . . . . . X . . . . . . X . . . . . . . . . . . . . . . . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t . . . . . X . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . X .
The number of ops, m x n: 2205 2205
The common substrings of size >= 4 are: seen war the dead the
The input strings are: seriously? why just why?! why so serious?
All the matches are: w h y s o s e r i o u s ? s . . . . X . . X . . . . . X . e . . . . . . . . X . . . . . . r . . . . . . . . . X . . . . . i . . . . . . . . . . X . . . . o . . . . . X . . . . . X . . . u . . . . . . . . . . . . X . . s . . . . X . . X . . . . . X . l . . . . . . . . . . . . . . . y . . X . . . . . . . . . . . . ? . . . . . . . . . . . . . . X . . . X . . X . . . . . . . . w X . . . . . . . . . . . . . . h . X . . . . . . . . . . . . . y . . X . . . . . . . . . . . . . . . X . . X . . . . . . . . j . . . . . . . . . . . . . . . u . . . . . . . . . . . . X . . s . . . . X . . X . . . . . X . t . . . . . . . . . . . . . . . . . . X . . X . . . . . . . . w X . . . . . . . . . . . . . . h . X . . . . . . . . . . . . . y . . X . . . . . . . . . . . . ? . . . . . . . . . . . . . . X ! . . . . . . . . . . . . . . .
The number of ops, m x n: 375 375
The common substrings of size >= 3 are: why why serious
The input strings are: smartphones are a gift from technology for human kind technology is getting smarter every day
All the matches are: t e c h n o l o g y i s g e t t i n g s m a r t e r e v e r y d a y s . . . . . . . . . . . . X . . . . . . . . . X . . . . . . . . . . . . . . . . m . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . a . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . X . r . . . . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . X . . . . . t X . . . . . . . . . . . . . . . X X . . . . . . . . X . . . . . . . . . . . . p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . h . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . X . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . n . . . . X . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . e . X . . . . . . . . . . . . . X . . . . . . . . . . . X . . X . X . . . . . . s . . . . . . . . . . . . X . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . a . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . X . r . . . . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . X . . . . . e . X . . . . . . . . . . . . . X . . . . . . . . . . . X . . X . X . . . . . . . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . a . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . X . . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . g . . . . . . . . X . . . . . X . . . . . X . . . . . . . . . . . . . . . . . . i . . . . . . . . . . . X . . . . . . X . . . . . . . . . . . . . . . . . . . . f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t X . . . . . . . . . . . . . . . X X . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . r . . . . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . X . . . . . o . . . . . X . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . m . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . t X . . . . . . . . . . . . . . . X X . . . . . . . . X . . . . . . . . . . . . e . X . . . . . . . . . . . . . X . . . . . . . . . . . X . . X . X . . . . . . c . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . h . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . n . . . . X . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . o . . . . . X . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . l . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . X . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . g . . . . . . . . X . . . . . X . . . . . X . . . . . . . . . . . . . . . . . . y . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . X . . . X . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . X . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . r . . . . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . X . . . . . . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . h . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . m . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . a . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . X . n . . . . X . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . X . . . . . . . X . . . . . . . X . . . . . X . . . k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i . . . . . . . . . . . X . . . . . . X . . . . . . . . . . . . . . . . . . . . n . . . . X . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . .
The number of ops, m x n: 2067 2067
The common substrings of size >= 5 are: technology smart
The input strings are: He has a cat She has a dog
All the matches are: S h e h a s a d o g H . . . . . . . . . . . . . e . . X . . . . . . . . . . . . . X . . . X . X . . . h . X . . X . . . . . . . . a . . . . . X . . X . . . . s . . . . . . X . . . . . . . . . X . . . X . X . . . a . . . . . X . . X . . . . . . . X . . . X . X . . . c . . . . . . . . . . . . . a . . . . . X . . X . . . . t . . . . . . . . . . . . .
The number of ops, m x n: 156 156
The common substrings of size >= 3 are: e has a