B. Password

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

//Codeforces Beta Round #93 (Div. 1 Only)
public class Password {
	public static void main(String[] args) throws IOException {
		BufferedReader buf = new BufferedReader(
				new InputStreamReader(System.in));
		String line = buf.readLine();
		char[] S = line.toCharArray();
		int start = zfunction(S);
		if (start == -1)
			System.out.println("Just a legend");
		else
			System.out.println(line.substring(0, start));
	}

	private static int zfunction(char[] S) {
		int L = 0;
		int R = 0;
		int n = S.length;
		int[] Z = new int[n];
		for (int i = 0; i < n; i++) {
			if (i > R) {
				L = R = i;
				while (R < n && S[R - L] == S[R])
					R++;
				Z[i] = R - L;
				R--;
			} else {
				int k = i - L;
				if (Z[k] < R - i + 1) {
					Z[i] = Z[k];
				} else {
					L = i;
					while (R < n && S[R - L] == S[R])
						R++;
					Z[i] = R - L;
					R--;
				}
			}
		}
		ArrayList<obj> list = new ArrayList<obj>();
		int index = 1;
		while (index < n - 1) {
			if (Z[index] == n - index)
				list.add(new obj(Z[index++] - 1, 0));
			else
				list.add(new obj(Z[index++], 0));

		}
		index = 1;
		while (index < n)
			if (Z[index] == n - index)
				list.add(new obj(Z[index++], 1));
			else
				index++;
		Collections.sort(list);
		for (int i = 0; i < list.size(); i++)
			if (list.get(i).type == 0) {
				while (i < list.size()) {
					if (list.get(i).type == 1)
						return list.get(i).len;
					i++;
				}
			}
		return -1;
	}

	static class obj implements Comparable<obj> {
		int type;
		int len;

		public obj(int l, int t) {
			type = t;
			len = l;
		}

		@Override
		public int compareTo(obj o) {
			if (len != o.len)
				return o.len - len;
			return type - o.type;
		}
	}
}

263. Period

#include <iostream>
#include <stdio.h>

using namespace std;
string c;
int f[1000001];
int get(char a, int l) {
		while (l != 0 && a != c[l])
			l = f[l - 1];
		if (a == c[l])
			return l + 1;
		else
			return l;
	}
int main()
{
    int t;
    scanf("%d",&t);
    for (int i=1;i<=t;i++)
    {
        int n;
        scanf("%d",&n);
        cin  >>c;
        f[0] = 0;
        for (int j = 1; j < n; j++)
				f[j] = get(c[j], f[j - 1]);
			printf("Test case #%d\n", i);
			for (int j = 1; j < n; j++) {
				if ((j + 1) % (j + 1 - f[j]) == 0 && f[j] != 0)
                {cout << (j + 1) << " "
                        <<((j + 1) / (j + 1 - f[j])) << endl;
			}
			}
            printf("\n");

    }
    return 0;
}