Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.81 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. public class homework {
  4. static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  5. static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  6. static StringTokenizer st;
  7. public static void main(String[] args) throws IOException {
  8. String s1 = next(), s2 = next();
  9. long hash1[] = new long[s1.length()+1], hash2[] = new long[s2.length()+1];
  10. long pow[] = new long[s1.length()+1], base = 131;
  11. pow[0] = 1;
  12. for(int i=1; i<=s1.length(); i++) {
  13. hash1[i] = hash1[i-1] * base + s1.charAt(i-1);
  14. pow[i] = pow[i-1] * base;
  15. }
  16. for(int i=1; i<=s2.length(); i++) {
  17. hash2[i] = hash2[i-1] * base + s2.charAt(i-1);
  18. }
  19. int ans = 0;
  20. for(int i=1; i<=Math.min(s1.length(), s2.length()); i++) {
  21. long t1 = getSubHash(hash1, pow, s1.length()-i+1, s1.length());
  22. long t2 = getSubHash(hash2, pow, 1, i);
  23. if(t1 == t2) ans = i;
  24. // System.out.println(s1.substring(s1.length()-i, s1.length()) + " " + t1 + "..." +
  25. // s2.substring(0, i) + " " + t2);
  26. }
  27. System.out.println(s1 + s2.substring(ans));
  28. }
  29. static long getSubHash(long hash[], long pow[], int l, int r) {
  30. return hash[r] - hash[l-1] * pow[r-l+1];
  31. }
  32. static String next () throws IOException {
  33. while (st == null || !st.hasMoreTokens())
  34. st = new StringTokenizer(br.readLine().trim());
  35. return st.nextToken();
  36. }
  37. static long readLong () throws IOException {
  38. return Long.parseLong(next());
  39. }
  40. static int readInt () throws IOException {
  41. return Integer.parseInt(next());
  42. }
  43. static double readDouble () throws IOException {
  44. return Double.parseDouble(next());
  45. }
  46. static char readCharacter () throws IOException {
  47. return next().charAt(0);
  48. }
  49. static String readLine () throws IOException {
  50. return br.readLine().trim();
  51. }
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement