Strings

finding a string within a string

not in n^2 time...i've never had to use this ever

/**
 * String matching: finds first index where token appears in string
 * @param s string to be searched
 * @param t token you're searching for
 * @return index where token is found, -1 if not found
 */
public int stringFind( String s, String t ){
	int f[] = new int[t.length()+1];
	for( int i = 2; i <= t.length(); i++ ){
		int j = f[i-1];
		do{
			if( t.charAt(j) == t.charAt(i-1) ){
				f[i] = j+1;
				break;
			}
			j = f[j];
		}while( j > 0 );
	}
	int i = 0, j = 0;
	while( i+j < s.length() ){
		if( j == t.length() ) return i;
		if( s.charAt(i+j) == t.charAt(j) ) j++;
		else if( j > 0 ){
			i += j - f[j];
			j = f[j];
		}
		else i++;
	}
	return -1;
}