Commit749eb78

committed

add substring with concatenation

1 parentf2f4e03 commit749eb78Copy full SHA for 749eb78

File tree

+36

-2

lines changed

+36

-2

lines changed

Lines changed: 36 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,38 @@`
	`1`	`+##[Space-time tradeoff](http://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff)`
`1`	`2`
`2`		`-##TODO`
`3`		`-* write down thinking`
	`3`	`+A brute force solution is easy. Yet, obviously, time limited.`
`4`	`4`
	`5`	`+###Check concatenation using count sum`
	`6`	`+`
	`7`	+cut a string`S` into N substring, lets say`s1 * 1, s2 * 2, s3 * 1`,
	`8`	+that is,`S` could be`s2s1s2s3` or`s3s1s2s2` or some string else.
	`9`	`+`
	`10`	+convert`L` to count sum, which is a map of`string to count`
	`11`	`+`
	`12`	+```
	`13`	`+M = empty Map`
	`14`	`+`
	`15`	`+for s in L`
	`16`	`+ M[s] = M[s] + 1`
	`17`	`+`
	`18`	`+`
	`19`	+```
	`20`	`+`
	`21`	`+`
	`22`	`+check concatenation S by minus count`
	`23`	`+`
	`24`	+```
	`25`	`+cut S into substrings by some length`
	`26`	`+`
	`27`	`+_M = clone of M`
	`28`	`+`
	`29`	`+for s in substrings`
	`30`	`+`
	`31`	`+ if _M[s] == 0`
	`32`	`+ Not a concatenation`
	`33`	`+`
	`34`	`+ _M[s] = _M[s] - 1`
	`35`	`+`
	`36`	`+`
	`37`	`+`
	`38`	+```

Comments

(0)