#!/usr/bin/perl
# 
# So, since everybody is tuning and tweaking their stuff, I figured I'd
# try playing with those optimizations again. Nothing as clever as some
# folks here have done, but I've managed to cut the times down pretty
# radically: well under 2 seconds for the Constitution, .8 seconds for
# 10000 "A"s, 51 minutes for "Tristram", etc. Doesn't seem like the exit
# tests should have made that much difference, but... I'm willing to
# believe empirical evidence. :)
# 
# ------------------------------------------------------------------------
# Created by Ben Okopnik on Thu Oct 17 09:25:20 EDT 2002

sub repeated_substring {
	$str = shift;
	$strlen = length $str;
	$longest = "";
	
	return "" unless $str =~ /(.).*\1/;
	$off = 0;
	$len = 1;
	
	{
		$match = substr $str, $off, $len;
		if ( ( substr $str, $off + $len ) =~ /\Q$match\E/ ){
			$longest = $match;
			return $longest if ( $off + $len * 3 - 1 ) > $strlen;
			$len++;
		}
		else{
			return $longest if ( $off + $len * 2 + 1 ) > $strlen;
			$off++;
		}
		redo;
	}
}

{
	local $/;
	( $string = <> ) =~ s/\n//g;
}

print repeated_substring $string
