You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S:"barfoothefoobarman"
L:["foo", "bar"]

You should return the indices:[0,9].
(order does not matter).

https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/

思路1：假设L中的单位长度为n，依次从S中取长度为n的子串，如果在L中，就记下来。需要借助hash或map，如果整个L都匹配完了，就算是一个concatenation；当匹配错误的时候，S右移一个位置。

思路2（参考2）：优化，双指针法，思想类似 Longest Substring Without Repeating Characters， 复杂度可以达到线性。

思路1：

public class Solution {	public ArrayList<Integer> findSubstring(String S, String[] L) {		if (S == null || L == null)			return null;		int size = L.length;		int len = L[0].length();		ArrayList<Integer> res = new ArrayList<Integer>();		HashMap<String, Integer> expected = new HashMap<String, Integer>();		for (String each : L) {			Integer old = expected.get(each);			if (old == null)				expected.put(each, 1);			else				expected.put(each, old + 1);		}		HashMap<String, Integer> real = new HashMap<String, Integer>();		int i;		for (i = 0; i <= S.length() - size * len; i++) {			real.clear();			int j, k = 0;			for (j = i; j < i + size * len; j = j + len, k++) {				String sub = S.substring(j, j + len);				if (expected.containsKey(sub)) {					Integer old = real.get(sub);					if (old == null)						real.put(sub, 1);					else						real.put(sub, old + 1);					if (real.get(sub) > expected.get(sub))						break;				} else					break;			}			if (k == size)				res.add(i);		}		return res;	}	public static void main(String[] args) {		// String S = "barfoothefoobarman";		// String[] L = { "foo", "foo" };		// System.out.println(new Solution().findSubstring(S, L));		String S = "a";		String[] L = { "a" };		System.out.println(new Solution().findSubstring(S, L));	}}

思路2（待实现中）：

参考：

http://blog.csdn.net/ojshilu/article/details/22212703

http://blog.csdn.net/linhuanmars/article/details/20342851