/* * Warmup Contest #1, September 1, 2010 Problem C * Solution by Tom Conerly * Originally from http://www.csc.kth.se/contest/boi/radio.pdf * Baltic Olympiad in Informatics 2009 radio * * First observe that we can assume that the repeating message S' * starts at the beginning of S (the input string). For the example * S = cabcabca and if S' = abc (not starting at the beginning) there * is a solution where it does start at the beginning (S' = cab). * * Assume that the answer is K consider writing S then on the line below * writing S shifted K characters to the right. For example * * cabcabca * cabcabca * * Notice that the strings line up. It is simple to see that the first K * characters of the string are the repeating portion. Notice that for the * strings to lineup the suffix of S must match the prefix of S. Thus the * problem reduces to finding the smallest K such that: * * The suffix of S of length |S|-K is the same as the prefix of S of length |S|-K. * * We could try each K and compare but there are O(L) values of K and each one * can take up to O(L) to compute giving an O(L^2) algorithm. * * FIRST SOLUTION: * One common trick for solving a large number of related string equality tests is * hashing. The high level idea is to hash both strings and check if the hash matches. * If we pick our hash function correctly we can compute it very quickly. * * For this problem polynomial hashing works well. If we have a string A of length N * the hash would be: * (A[0]x^0 + A[1]x^{1} + ... + A[N-2]x^{N-2} + A[N-1]x^{N-1}) mod P * Where P is normally a prime and x is an arbitrary value. * * If we have computed this hash for the first N-1 characters of A we can compute * the hash of A in constant time. Thus we can compute the hash of all prefixes * and suffixes of S in O(L) time. * * The algorithm is now go from smallest K to largest and check if the hash matches. * If it does it could still be a collision so actually check that the strings match. * It turns out that collisions are very very unlikely so you don't even need to check * them. * * SECOND SOLUTION: * This can be solved by Knuth–Morris–Pratt algorithm (Google for a description). I'm * not going to write up a description of the algorithm it should be in CLRS and online. * */ import java.io.*; public class C { //There are two different solutions change solve to solve2 in the main function //to run the other solution public static void main(String[] args) throws Exception{ //The input can be huge so use BufferedReader not Scanner BufferedReader R = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.valueOf(R.readLine()); String S = R.readLine(); System.out.println(solve(N, S)); } //Solves using string polynomial hashing. public static int solve2(int N, String S){ long[] HL = new long[N]; long[] HR = new long[N]; long pow = 17; long cur = 1; long prev = 0; //Compute the hash of the prefixes for(int i = 0; i < N;i++){ prev = cur*(S.charAt(i)-'a')+prev; cur *= pow; HL[i] = prev; } //compute the hash of the suffixes prev = 0; for(int i = N-1; i >= 0;i--){ prev = (S.charAt(i)-'a')+pow*prev; HR[i] = prev; } //find the first hash that matches for(int i = 1; i < N;i++) if(HL[N-i-1] == HR[i]) return i; return N; } //Solves using KMP public static int solve(int N, String S){ int[] F = new int[N+1]; int at = 0; for(int i = 2; i < N;i++){ while(at > 0 && S.charAt(i-1) != S.charAt(at)) at = F[at]; if(S.charAt(i-1) == S.charAt(at)) F[i] = ++at; } at = 0; for(int i = 1; i < N; i++){ while(at > 0 && S.charAt(at) != S.charAt(i)) at = F[at]; if(S.charAt(at) == S.charAt(i)) at++; } return N-at; } }