import java.util.*;

/**
   Carry out preprocessing in accordance with D.Gusfield: Algorithms on
   Strings, Trees, and sequences
 */
public class ZPreProcess
{
    private char[]  _pattern; // The pattern we are looking for
    private int[]   _z;	      // The corresponding Z array of matches

    /** We are comparing characters at pattern[t+x] and text[p+x]
	incrementing x (initially 0) as long as they remain equal.
	We return the number of matches found.
     */
    private static int biScan(char[] pattern, int t, char[] text, int p) {
	int count = 0;
	while ((t+count < pattern.length) && (p + count < text.length)
		&& pattern[t+count] == text[p + count])
		count++;
	return count;
    }

    public String toString() {
	String s = 
	    "The Z  array for the pattern\n    " +
	    (new String(_pattern)) + "\nis\n";
	for (int a: _z)
	    s += "    " + a;
	return s;
    }

    public ZPreProcess(String pattern) {
	_pattern = pattern.toCharArray();
	_z = new int[pattern.length()];
	if (pattern.length() < 2) return;
	int l = 0;
	int r = 0;
	_z[1] = biScan(_pattern, 0, _pattern, 1);
	if (_z[1] != 0) {
	    l = 1;
	    r = _z[1];
	}
//	System.out.println("k="+1+", l="+l+", r="+r+", _z[k]="+_z[1]);
	for (int k = 2; k < _pattern.length; k++) {
	    if (r < k) {
		int n = biScan(_pattern, 0, _pattern, k);
		if (n == 0) {
		    l = r = _z[k] = 0;
		} else {
		    l = k;
		    r = k + n - 1;
		    _z[k] = n;
		}
	    } else {
	        int h = k - l;
	        if (_z[h] < (r - k + 1)) {
		    _z[k] = _z[h];
	    	} else {
		    int n = biScan(_pattern, r - l - h + 1, _pattern, r+1);
		    l = k;
		    r += n;
		    _z[k] = r - k + 1;
	    	}
	    }
//	    System.out.println("k="+k+", l="+l+", r="+r
//		+", _z[k]="+_z[k]);
	}
    }


    /** It returns a list of all the locations where the pattern P
	occurs in the text T
     */
    public ArrayList<Integer> findPlaces(String T) {
	ArrayList<Integer> places = new ArrayList<Integer>();
	char[] text = T.toCharArray();
	int l = 0;
	int r = 0;
	int z = 0;
	for (int k = 0; k < text.length - _pattern.length + 1; k++) {
	    if (r <= k) {
		int n = biScan(_pattern, 0, text, k);
		if (n == 0) {
		    l = r = z = 0;
		} else {
		    l = k;
		    r = k + n - 1;
		    z = n;
		}
	    } else {
	        int h = k - l;
	        if (_z[h] < (r - k + 1)) {
		    z = _z[h];
	    	} else {
		    int n = biScan(_pattern, r-l-h+1, text, r+1);
		    l = k;
		    r += n;
		    z = r - k + 1;
	    	}
	    }
//	    System.out.println("k="+k+", l="+l+", r="+r
//		+", z="+z);
	    if (z >= _pattern.length)
		places.add(k);
	}
	return places;
    }

    public static void main(String[] args) {
	if (args.length < 2 || args[0].length() < 2) {
	    System.out.println("Usage: java ZPreProcess patterString textString");
	    return;
	}
	ZPreProcess z = new ZPreProcess(args[0]);
	System.out.println(z);
	// Now we want to look for all the places where the string args[0]
	// i.e. P occurs in the string args[1] i.e. T.
	ArrayList<Integer> places = z.findPlaces(args[1]);
	if (places.size() == 0)
	    System.out.println(args[0] + " does not occur in " + args[1]);
	else {	
	    System.out.println(args[0] + " occurs in " + args[1] +
		" at positions:");
	    for (Integer who: places)
		System.out.println("\t" + who);
	}
    }
}