Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class homework {
- static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- static StringTokenizer st;
- public static void main(String[] args) throws IOException {
- String s1 = next(), s2 = next();
- long hash1[] = new long[s1.length()+1], hash2[] = new long[s2.length()+1];
- long pow[] = new long[s1.length()+1], base = 131;
- pow[0] = 1;
- for(int i=1; i<=s1.length(); i++) {
- hash1[i] = hash1[i-1] * base + s1.charAt(i-1);
- pow[i] = pow[i-1] * base;
- }
- for(int i=1; i<=s2.length(); i++) {
- hash2[i] = hash2[i-1] * base + s2.charAt(i-1);
- }
- int ans = 0;
- for(int i=1; i<=Math.min(s1.length(), s2.length()); i++) {
- long t1 = getSubHash(hash1, pow, s1.length()-i+1, s1.length());
- long t2 = getSubHash(hash2, pow, 1, i);
- if(t1 == t2) ans = i;
- // System.out.println(s1.substring(s1.length()-i, s1.length()) + " " + t1 + "..." +
- // s2.substring(0, i) + " " + t2);
- }
- System.out.println(s1 + s2.substring(ans));
- }
- static long getSubHash(long hash[], long pow[], int l, int r) {
- return hash[r] - hash[l-1] * pow[r-l+1];
- }
- static String next () throws IOException {
- while (st == null || !st.hasMoreTokens())
- st = new StringTokenizer(br.readLine().trim());
- return st.nextToken();
- }
- static long readLong () throws IOException {
- return Long.parseLong(next());
- }
- static int readInt () throws IOException {
- return Integer.parseInt(next());
- }
- static double readDouble () throws IOException {
- return Double.parseDouble(next());
- }
- static char readCharacter () throws IOException {
- return next().charAt(0);
- }
- static String readLine () throws IOException {
- return br.readLine().trim();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement