KMP
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```csharp []
public class Solution {
    private int[] PrefixTarget(string s)
    {
        int len = s.Length;
        int[] preArr = new int[len];

        for(int i = 1; i < len; i++)
        {
            int j = preArr[i-1];
            while(j > 0 && s[i] != s[j])
            {
                j = preArr[j-1];
            }

            if(s[i] == s[j])
                j++;

            preArr[i] = j;
        }

        return preArr;
    }
    public int MinValidStrings(string[] words, string target) {
        int len = words.Length, lenT = target.Length;
        int[] dist = new int[lenT+1];
        
        foreach(string w in words)
        {
            int[] preArr = PrefixTarget(w+"#"+target);
            int wLen = w.Length;
            for(int i = 1; i <= lenT; i++)
            {
                dist[i] = Math.Max(dist[i], preArr[wLen+i]);
            }
        }

        int curLen = lenT, res = 0;
        while(curLen > 0 && dist[curLen] > 0)
        {
            curLen -= dist[curLen];
            res++;
        }

        return curLen == 0 ? res : -1;
    }
}
```
['C#']