acm-2008-A-string LD

Problem A: String LD
Stringld (left delete) is a function that gets a string and deletes its leftmost character (for instance
Stringld(“acm”) returns “cm”).
You are given a list of distinct words, and at each step, we apply stringld on every word in the list. Write a program
that determines the number of steps that can be applied until at least one of the conditions become true:
1) A word becomes empty string, or
2) a duplicate word is generated.
For example, having the list of words aab, abac, and caac, applying the function on the input for the first time results
in ab, bac, and aac. For the second time, we get b, ac, and ac. Since in the second step, we have two ac strings, the
condition 2 is true, and the output of your program should be 1. Note that we do not count the last step that has resulted
in duplicate string. More examples are found in the sample input and output section.
Input (Standard Input)
There are multiple test cases in the input. The first line of each test case is n (1  n  100), the number of words.
Each of the next n lines contains a string of at most 100 lower case characters.
The input terminates with a line containing 0.
Output (Standard Output)
For each test case, write a single line containing the maximum number of stringld we can call.
Sample Input and Output
Standard Input Standard Output

مسئله الف: رشته LD

رشته حذف چپ یا Stringld، تابعی است که یک رشته را می گیرد و چپ ترین کاراکتر آنرا حذف می کند (برای مثال stringld(“acm”) رشته “cm” را بر می گرداند. لیستی از کلمات مجزا و متفاوت به شما داده می شود،‌ و در هر مرحله، ما تابع stringld را برای تمامی رشته در لیست اجرا می کنیم. برنامه ای بنویسید که تعداد مراحلی را که با دو شرط زیر پذیرفته می شود را نمایش بدهد:

1. رشته تبدیل به تهی (empty) شود، یا
2. رشته های شبیه به هم ایجاد شوند

برای مثال ما لیست کلمات aab, abac و caac را داریم،‌ استفاده از تابع برای اولین بار مقادیر bac, ab و aac را برمی گرداند. برای بار دوم، ما ۲ تا رشته ac داریم که بنا به شرط ۲ قبول می شود و خروجی برنامه ما عدد ۱ می شود. تذکر این که ما تعداد کلمات تکراری در آخرین مرحله را نمی خواهیم. مثال های بیشتری را می توانید در قسمت ورودی و خروجی مشاهده کنید.

ورودی

تعدادی test case برای ورودی آورده شده است. اولین خط از ورودی n(1<= n <= 100) می باشد که تعداد کلمات را مشخص می کند. تعداد n خط بعدی شامل رشته هایی است که زیر 100 مورد هست. ورودی با مقدار 0 در یک خط به پایان می رسد.

خروجی

برای هر test case، یک خط چاپ کنید که بیشترین تعداد فراخوانی تابع stringld را نمایش بدهد.

نمونه ای از ورودی و خروجی

دانلود فایل ورودی

دانلود فایل خروجی

جواب مسئله به زبان Java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class acm2008a {

	public static void main(String[] args) {
		List<String> fileContent = readFromFile("C:\\a.in");
		int fileContentLine = 0;
		
		while (!fileContent.get(fileContentLine).equals("0")) {
			Map<Integer, String> inputMap = new HashMap<Integer, String>();
			int numberOfLine = Integer.parseInt(fileContent.get(fileContentLine++));
			
			for (int i=fileContentLine; i< numberOfLine+fileContentLine; i++) {
				inputMap.put(i, fileContent.get(i));
			}
			fileContentLine += numberOfLine;
			
			boolean flag = false;
			int step = 0;
			do {
				for (Integer key : inputMap.keySet()) {
					inputMap.put(key, stringld(inputMap.get(key)));
				}
				
				for (Integer key : inputMap.keySet()) {
					if (inputMap.get(key) == null || checkDuplicateWord(inputMap, key)) {
						System.out.println(step);
						flag = true;
						break;
					}
				}
				step++;
			} while(!flag);
		}
	}
	
	public static String stringld(String str) {
		if (str.length() == 1)
			return null;
		return str.substring(1, str.length());
	}
	
	public static boolean checkDuplicateWord(Map<Integer, String> wordMap, Integer wordKey) {
		List<String> wordList = new ArrayList<String>();
		String word = "";
		for (Integer key : wordMap.keySet()) {
			if (key.equals(wordKey))
				word = wordMap.get(key);
			else
				wordList.add(wordMap.get(key));
		}
		if (wordList.contains(word))
			return true;
		return false;
	}
	
	public static List<String> readFromFile(String path) {
		List<String> fileContent = new ArrayList<String>();
		File fileToRead = new File(path);

		try( FileReader fileStream = new FileReader( fileToRead ); 
		    BufferedReader bufferedReader = new BufferedReader( fileStream ) ) {

		    String line = null;

		    while( (line = bufferedReader.readLine()) != null ) {
		    	fileContent.add(line);
		    }

		    } catch ( FileNotFoundException ex ) {
		        ex.printStackTrace();
		    } catch ( IOException ex ) {
		    	ex.printStackTrace();
		}
		return fileContent;
	}

}