lelooo

class Solution
{
    
    ArrayList<Integer> search(String pat, String txt)
    {
        // your code here
        int n = pat.length();
        int m = txt.length();
        int[] lps = new int[n+m+1];
        
        String str = pat + "#"+txt;
        
        char[] arr =  str.toCharArray();
        
        int i = 1 ;
        int len = 0 ;
        lps[0] = 0 ;
        
        while(i<arr.length)
        {
            if(arr[i] == arr[len])
            {
                len +=1;
                lps[i] = len;
                i+=1;
            }else {
                if(len > 0){
                    len = lps[len-1];
                }else {
                    lps[i] = 0 ;
                    i++;
                }
            }
        }
        
       // System.out.println(Arrays.toString(lps) + "   "  + n);
        
        ArrayList<Integer> out = new ArrayList<>();
        
        int itr = n;
        
        for(;itr<lps.length;itr++) if(lps[itr] == n) out.add(itr- 2*n + 1);
        
        return out;
    }
}