Jovfer

Untitled

Nov 4th, 2013
227
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.73 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.Arrays;
  3. import java.util.StringTokenizer;
  4.  
  5. public class taskE {
  6.  
  7.     StringTokenizer st;
  8.     BufferedReader in;
  9.     PrintWriter out;
  10.  
  11.     public static void main(String[] args) throws NumberFormatException,
  12.             IOException {
  13.         taskE solver = new taskE();
  14.         solver.open();
  15.         long time = System.currentTimeMillis();
  16.         solver.solve();
  17.         /* if (!"true".equals(System.getProperty("ONLINE_JUDGE"))) {
  18.          System.out.println("Spent time: "
  19.          + (System.currentTimeMillis() - time));
  20.          System.out.println("Memory: "
  21.          + (Runtime.getRuntime().totalMemory() - Runtime
  22.          .getRuntime().freeMemory()));
  23.          } */
  24.         solver.close();
  25.     }
  26.  
  27.     public void open() throws IOException {
  28.         //in = new BufferedReader(new InputStreamReader(System.in));
  29.         //out = new PrintWriter(System.out);
  30.         in = new BufferedReader(new FileReader("input.txt"));
  31.         out = new PrintWriter(new FileWriter("output.txt"));
  32.     }
  33.  
  34.     public String nextToken() throws IOException {
  35.         while (st == null || !st.hasMoreTokens()) {
  36.             String line = in.readLine();
  37.             if (line == null) {
  38.                 return null;
  39.             }
  40.             st = new StringTokenizer(line);
  41.         }
  42.         return st.nextToken();
  43.     }
  44.  
  45.     public int nextInt() throws NumberFormatException, IOException {
  46.         return Integer.parseInt(nextToken());
  47.     }
  48.  
  49.     public long nextLong() throws NumberFormatException, IOException {
  50.         return Long.parseLong(nextToken());
  51.     }
  52.  
  53.     public double nextDouble() throws NumberFormatException, IOException {
  54.         return Double.parseDouble(nextToken());
  55.     }
  56.  
  57.     boolean hasMoreTokens() throws IOException {
  58.         while (st == null || !st.hasMoreTokens()) {
  59.             String line = in.readLine();
  60.             if (line == null) {
  61.                 return false;
  62.             }
  63.             st = new StringTokenizer(line);
  64.         }
  65.         return true;
  66.     }
  67.  
  68.     int n;
  69.  
  70.     private int getPrefixLength(String a, int posA, String b, int posB) {
  71.         int result = 0;
  72.         while (result + posA < a.length() && result + posB < b.length() && a.charAt(result + posA) == b.charAt(result + posB)) {
  73.             result++;
  74.         }
  75.         return result;
  76.     }
  77.  
  78.     private boolean slv(String str, int pos, int ind) {
  79.         boolean result = false;
  80.         if (isChecked[ind][pos]) {
  81.             return false;
  82.         }
  83.         isChecked[ind][pos] = true;
  84.         int com;
  85.         int strL = str.length();
  86.  
  87.         for (int i = 0; i < dict.length && !result; i++) {
  88.             int curL = dict[i].length();
  89.             if (pos + curL == strL) {
  90.                 int h1 = (int)(1L*hashInp[i][curL - 1] * pp[pos]) % MOD;
  91.                 int h2 = (hashInp[ind][strL - 1] - hashInp[ind][pos-1])%MOD;
  92.                 if (h1 == h2)
  93.                     return true;
  94.             } else if (pos + curL > strL) {
  95.                 com = strL - pos;
  96.                 int h1 = (int)(1L*hashInp[i][com - 1] * pp[pos]) % MOD;
  97.                 int h2 = (hashInp[ind][strL - 1] - hashInp[ind][pos-1])%MOD;
  98.                 if (h1 == h2)
  99.                     if (!isChecked[i][com]) {
  100.                         result |= slv(dict[i], com, i);
  101.                     }
  102.             } else {
  103.                 com = curL;
  104.                 int h1 = (int)(1L*hashInp[i][com - 1] * pp[pos]) % MOD;
  105.                 int h2 = (hashInp[ind][pos+curL - 1] - hashInp[ind][pos-1])%MOD;
  106.                 if (h1 == h2) {
  107.                     boolean notChecked = !isChecked[ind][pos + com];
  108.                     if (notChecked) {
  109.                         result |= slv(str, pos + com, ind);
  110.                     }
  111.                 }
  112.             }
  113.         }
  114.         return result;
  115.     }
  116.  
  117.     String[] dict;
  118.     boolean[][] isChecked;
  119.     int[][] hashInp;
  120.     int p = 513;
  121.     int[] pp = new int[(int) (5 * 1e5)];
  122.  
  123.     static final int MOD = (int) (1e9 + 7);
  124.  
  125.     public void solve() throws NumberFormatException, IOException {
  126.         n = nextInt();
  127.         dict = new String[n];
  128.         isChecked = new boolean[n][];
  129.         hashInp = new int[n][];
  130.         for (int i = 0; i < dict.length; i++) {
  131.             dict[i] = in.readLine();
  132.         }
  133.         pp[0] = 1;
  134.         for (int i = 1; i < pp.length; i++) {
  135.             pp[i] = (int)(1L* pp[i - 1] * p) % MOD;
  136.         }
  137.         Arrays.sort(dict);
  138.         for (int i = 0; i < dict.length; i++) {
  139.             isChecked[i] = new boolean[dict[i].length()];
  140.             isChecked[i][0] = false;
  141.             hashInp[i] = new int[dict[i].length()];
  142.             hashInp[i][0] = dict[i].charAt(0);
  143.             for (int j = 1; j < dict[i].length(); j++) {
  144.                 isChecked[i][j] = false;
  145.                 hashInp[i][j] =  (int)(hashInp[i][j - 1] + 1L *pp[j] * dict[i].charAt(j) %MOD) % MOD;
  146.             }
  147.         }
  148.         for (int i = 0; i < n - 1; i++) {
  149.             for (int j = i + 1; j < n; j++) {
  150.                 int ind = i;
  151.                 String a = dict[i];
  152.                 String b = dict[j];
  153.                 int com = getPrefixLength(a, 0, b, 0);
  154.                 if (com != Math.min(a.length(), b.length())) {
  155.                     continue;
  156.                 }
  157.                 if (b.length() > a.length()) {
  158.                     a = b;
  159.                     ind = j;
  160.                 }
  161.                 if (isChecked[ind][com]) {
  162.                     continue;
  163.                 }
  164.                 if (slv(a, com, ind)) {
  165.                     out.println("YES");
  166.                     return;
  167.                 }
  168.             }
  169.         }
  170.         out.println("NO");
  171.     }
  172.  
  173.     public void close() {
  174.         out.flush();
  175.         out.close();
  176.     }
  177. }
Advertisement
Add Comment
Please, Sign In to add comment