Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.Arrays;
- import java.util.StringTokenizer;
- public class taskE {
- StringTokenizer st;
- BufferedReader in;
- PrintWriter out;
- public static void main(String[] args) throws NumberFormatException,
- IOException {
- taskE solver = new taskE();
- solver.open();
- long time = System.currentTimeMillis();
- solver.solve();
- /* if (!"true".equals(System.getProperty("ONLINE_JUDGE"))) {
- System.out.println("Spent time: "
- + (System.currentTimeMillis() - time));
- System.out.println("Memory: "
- + (Runtime.getRuntime().totalMemory() - Runtime
- .getRuntime().freeMemory()));
- } */
- solver.close();
- }
- public void open() throws IOException {
- //in = new BufferedReader(new InputStreamReader(System.in));
- //out = new PrintWriter(System.out);
- in = new BufferedReader(new FileReader("input.txt"));
- out = new PrintWriter(new FileWriter("output.txt"));
- }
- public String nextToken() throws IOException {
- while (st == null || !st.hasMoreTokens()) {
- String line = in.readLine();
- if (line == null) {
- return null;
- }
- st = new StringTokenizer(line);
- }
- return st.nextToken();
- }
- public int nextInt() throws NumberFormatException, IOException {
- return Integer.parseInt(nextToken());
- }
- public long nextLong() throws NumberFormatException, IOException {
- return Long.parseLong(nextToken());
- }
- public double nextDouble() throws NumberFormatException, IOException {
- return Double.parseDouble(nextToken());
- }
- boolean hasMoreTokens() throws IOException {
- while (st == null || !st.hasMoreTokens()) {
- String line = in.readLine();
- if (line == null) {
- return false;
- }
- st = new StringTokenizer(line);
- }
- return true;
- }
- int n;
- private int getPrefixLength(String a, int posA, String b, int posB) {
- int result = 0;
- while (result + posA < a.length() && result + posB < b.length() && a.charAt(result + posA) == b.charAt(result + posB)) {
- result++;
- }
- return result;
- }
- private boolean slv(String str, int pos, int ind) {
- boolean result = false;
- if (isChecked[ind][pos]) {
- return false;
- }
- isChecked[ind][pos] = true;
- int com;
- int strL = str.length();
- for (int i = 0; i < dict.length && !result; i++) {
- int curL = dict[i].length();
- if (pos + curL == strL) {
- int h1 = (int)(1L*hashInp[i][curL - 1] * pp[pos]) % MOD;
- int h2 = (hashInp[ind][strL - 1] - hashInp[ind][pos-1])%MOD;
- if (h1 == h2)
- return true;
- } else if (pos + curL > strL) {
- com = strL - pos;
- int h1 = (int)(1L*hashInp[i][com - 1] * pp[pos]) % MOD;
- int h2 = (hashInp[ind][strL - 1] - hashInp[ind][pos-1])%MOD;
- if (h1 == h2)
- if (!isChecked[i][com]) {
- result |= slv(dict[i], com, i);
- }
- } else {
- com = curL;
- int h1 = (int)(1L*hashInp[i][com - 1] * pp[pos]) % MOD;
- int h2 = (hashInp[ind][pos+curL - 1] - hashInp[ind][pos-1])%MOD;
- if (h1 == h2) {
- boolean notChecked = !isChecked[ind][pos + com];
- if (notChecked) {
- result |= slv(str, pos + com, ind);
- }
- }
- }
- }
- return result;
- }
- String[] dict;
- boolean[][] isChecked;
- int[][] hashInp;
- int p = 513;
- int[] pp = new int[(int) (5 * 1e5)];
- static final int MOD = (int) (1e9 + 7);
- public void solve() throws NumberFormatException, IOException {
- n = nextInt();
- dict = new String[n];
- isChecked = new boolean[n][];
- hashInp = new int[n][];
- for (int i = 0; i < dict.length; i++) {
- dict[i] = in.readLine();
- }
- pp[0] = 1;
- for (int i = 1; i < pp.length; i++) {
- pp[i] = (int)(1L* pp[i - 1] * p) % MOD;
- }
- Arrays.sort(dict);
- for (int i = 0; i < dict.length; i++) {
- isChecked[i] = new boolean[dict[i].length()];
- isChecked[i][0] = false;
- hashInp[i] = new int[dict[i].length()];
- hashInp[i][0] = dict[i].charAt(0);
- for (int j = 1; j < dict[i].length(); j++) {
- isChecked[i][j] = false;
- hashInp[i][j] = (int)(hashInp[i][j - 1] + 1L *pp[j] * dict[i].charAt(j) %MOD) % MOD;
- }
- }
- for (int i = 0; i < n - 1; i++) {
- for (int j = i + 1; j < n; j++) {
- int ind = i;
- String a = dict[i];
- String b = dict[j];
- int com = getPrefixLength(a, 0, b, 0);
- if (com != Math.min(a.length(), b.length())) {
- continue;
- }
- if (b.length() > a.length()) {
- a = b;
- ind = j;
- }
- if (isChecked[ind][com]) {
- continue;
- }
- if (slv(a, com, ind)) {
- out.println("YES");
- return;
- }
- }
- }
- out.println("NO");
- }
- public void close() {
- out.flush();
- out.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment