Posts

Showing posts with the label KMP

1365. Minimum Cycle Section

Given an array of int, find the length of the minimum cycle section. The length of array do not exceed  100000 。 Each element is in the int range 。 Have you met this question in a real interview?    Yes Problem Correction Example Example 1 Input: [1,2,1,2,1,2] Output: 2 Explanation: The minimum cycle section is [1,2],and the length is 2. Example 2 Input: [1,2,1,2,1] Output: 2 Explanation: The minimum cycle section is [1,2],and the length is 2, although the last 2 is not given, we still consider the cycle section is [1,2]. Example 3 class Solution { public : /** * @param array: an integer array * @return: the length of the minimum cycle section */ int minimumCycleSection ( vector < int > & array ) { // Write your code here int *next = new int [ array .size() + 1 ]; int i = 0 , j = -1 ; next[ 0 ] = -1 ; while (i < array .size()) { ...