`
woxiaoe
  • 浏览: 284564 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

两道字符串的水题

    博客分类:
  • ACM
阅读更多

acm3080 acm1936

一个是求两个串的最长公共序列,一个是两个串的匹配

package com.woxiaoe.acm.pku.P1936;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class Main {
	
	public static void main(String[] args) {
		Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));
		//Scanner scn = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		List<String> data = new ArrayList<String>();
		while(scn.hasNext()){
			data.add(scn.next());
			
		}
		int len = data.size();
		String src = "";
		String desc = "";
		int r = 0;
		int cLen = 0;
		for(int i = 0; i < len; i++){
			int pre = -1;
			Set<Integer> vSet = new HashSet<Integer>();
			src = data.get(i);
			desc = data.get(++i);
			char[] c = src.toCharArray();
			cLen = c.length;
			for(int j = 0; j < cLen; j++){
				r = desc.indexOf((int)c[j]);
				while((vSet.contains(r) || r < pre) && r != -1){
					r = desc.indexOf((int)c[j],r + 1);
				}
				if(r != -1 && r > pre ){
					vSet.add(r);
					pre = r;
				}else{
					out.println("No");
					r = -1;
					break;
				}
			}
			if(r != -1){
				out.println("Yes");
			}
			r = 0;
		}
		out.flush();
	}

}
 package com.woxiaoe.acm.poj3080;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));
		//Scanner scn = new Scanner(System.in);
		int n,m = 0;
		List<String> data = null;;
		while(true){
			n = scn.nextInt();
			for(int i = 0; i < n; i++){
				data = new ArrayList<String>();
				m = scn.nextInt();
				for(int j = 0; j < m; j++){
					data.add(scn.next());
				}
				System.out.println(work(data,data.size()));
			}
			return;
			
		}
		
	}

	private static String work(List<String> data, int m) {
		String str = data.get(0);
		int len = str.length();
		String sub = "";
		String common = "";
		int size = 0;
		boolean find = false;
		for(int i = 0; i < len - 1; i++){
			for(int j = i; j < len; j++){
				sub = str.substring(i,j + 1);
				int k = 0;
				for(k = 1; k < m; k++){
					if(data.get(k).indexOf(sub) == -1){
						find = false;
						break;
					}
				}
				if(k == m){
					find = true;
				}
				if(find){//如果找到
					if(sub.length() < 3){
						continue;
					}
					if(sub.length() == size && common.compareTo(sub) > 0){
						common = sub;
					}else if(sub.length() > size){
						size = sub.length();
						common = sub;
					}
					
				}
			}
		}
		
		return size == 0?"no significant commonalities":common;
	}

}
 
分享到:
评论

相关推荐

    杭电的几道ACM水题

    3. 解决ACM水题:对于初学者,可以从简单的水题开始,比如实现基本的数学运算、字符串处理、排序和查找等。通过解决这些题目,可以逐渐熟悉编程环境,掌握基本算法,例如冒泡排序、快速排序、二分查找等。 4. 学习...

    数据结构算法面试题22道-含答案.pdf

    本文档共收录了22道数据结构算法面试题,涵盖了链表、树、字符串等多种数据结构,旨在帮助读者更好地理解和掌握数据结构算法。以下是对每道题的详细解释: 1. 反转一个链表(循环算法) 在这个问题中,我们需要...

    杭电152道水题 适合初学者参考

    这些"水题"通常指的是难度较低,适合新手练手的问题,旨在帮助初学者熟悉编程的基本概念和逻辑,增强编程思维。 1. **大整数加减乘【可运行】.cpp**:这个文件可能是实现大整数的加、减、乘运算的程序。在C++中处理...

    大厂算法面试题库中高频出现的30道典型题.pdf

    这个问题考察对滑动窗口技巧的掌握,需要在遍历字符串的同时保持一个窗口,该窗口内没有重复字符,并不断更新最长无重复字符的子串。 2. 将一个32位有符号整数中的数字进行反转。这需要考虑整数反转时的边界问题,...

    LeetCode判断字符串是否循环-ACMTraining:同步需求

    LeetCode判断字符串是否循环 Problem41 of LeetCode 题目: 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。 这道题体现了对数组信息维度的利用。利用好了可以在时间和空间复杂度上都有很大帮助 可以...

    194道C语言复习练习题及答案.pdf

    这里`s`是一个指向字符串的指针,通过`s += 1`使得指针移动一个字符的位置,因此输出从字符串的第二个字符开始,即`bcde`。 #### 题目15: 数组元素引用 **题目:** 若有定义:`int a[2][3];`则以下对`a`数组元素的...

    计算机二级考试-JAVA上机试题及答案 .pdf

    简单应用题中,考生需要设计一个具有两个文本框的程序,用户在 Input 文本框中输入字符串后回车,字符串会在 Output 文本框中出现。这道题考查了考生的事件处理和GUI 编程能力。 综合应用题中,考生需要设计一个...

    大厂算法面试题库中高频出现的30道典型题

    2. **逐字符比较**:从头开始逐个比较两个字符串的字符,直到遇到不相同的字符或者达到其中一个字符串的末尾为止。 #### 代码示例 ```java public String longestCommonPrefix(String[] strs) { if (strs.length =...

    2014华为校园招聘上机题

    【华为校园招聘上机题】涉及的编程与算法知识点广泛,包括数组操作、逻辑判断、字符串处理、数学问题以及数据结构。以下是对这些知识点的详细解释: 1. **去除最大值、最小值之后剩下的个数**:这道题目可能是要求...

    面试题面试题面试题34

    实现字符串翻转,可以使用双指针技术,一个从字符串开头开始,另一个从末尾开始,交换它们指向的字符,直到两个指针相遇。在设计测试用例时,应考虑包含特殊字符如“,”、“.”,以及空格、数字、大写字母等,还要...

    第四届和第五届全国信息技术大赛复赛试题

    程序首先确定字符串的长度,然后使用两个指针,一个指向字符串的起始位置,另一个指向末尾,通过交换对应位置的字符,逐步将字符串反转。这不仅是对指针操作熟练度的检验,也是对字符串处理技巧的考察。在实际编程中...

    西邮Linux兴趣小组2023年纳新一面题

    这道题目考察了函数的基本概念和字符串操作。函数welcome()应该返回一个字符串,即自己的姓名。在main函数中,我们可以使用函数welcome()来获取自己的姓名,并将其打印出来。 3. 指针和数组 这道题目考察了指针和...

    微软、谷歌、百度等公司经典面试100题[第101-170题].pdf

    - **题目描述**:实现类似于`malloc()`的功能以及复制两个字符串,其中一个字符串的部分内容与另一个字符串重叠。 - **解决方案** - **内存分配函数**:可以使用标准库中的`malloc()`函数作为参考,通过调用系统API...

    76道比较难的C语言题目

    - 使用循环结构来逐个字符地比较两个字符串。 ### 17. 字符串的状态转换 **题目描述**:题目要求实现字符串状态的转换功能。 **知识点**: - 状态机的基本概念。 - 如何根据输入的字符改变当前状态。 - 使用条件...

    详细华为面试题及答案

    需要注意的是,复制过程中必须为新字符串预留足够的空间,并确保在末尾添加空字符`\0`作为字符串的结束标志。 #### 题目六:函数类型定义与调用 这道题目展示了C语言中的函数类型定义和动态类型调用。通过`typedef`...

    LeetCode前400题Java精美版

    【LeetCode前400题Java精美版】是个人对LeetCode中前400道题目进行解答并整理的笔记,主要使用Java语言编写。这个资料的特点在于,它提供的解决方案多数情况下是经过优化的,能够击败99%的提交,即使在某些复杂问题...

    高职升本计算机C语言程序题-含答案.pdf

    * 知识点:字符串操作、循环语句、条件语句 * 应用场景:删除字符串中的指定字符 9.计算:n131211+++++ * 知识点:循环语句、赋值语句、累加语句 * 应用场景:计算指定的数学公式 10.实现累加输入整型变量...

    76道C或C++入门必做的编程题

    编写一个程序,输入字符串“ABCDE”,然后对每个字符进行替换,输出一个新的字符串。例如,将每个字符替换成不同的值,如D、F、G等,并确保输出的结果具有一定的规律性。 #### 关键知识点: - 字符串处理:学习如何...

    数据结构与算法 腾讯精选练习50 V1.0.pdf

    这一部分具体包括了LeetCode平台上的经典练习题,腾讯精选的50道题目,这些题目旨在帮助学习者加深对数据结构与算法的理解并能应用于实际问题解决。 描述中提到这本册子可以作为数据结构与算法课程的学习参考资料,...

    2023蓝电考核题.pdf

    5. 将一个字符串逆序输出:这道题目考察了C语言的字符串处理知识。学生需要编写一个C程序,输入一个字符串,然后将该字符串逆序输出。 单片机应用部分 A组: 1. 独立按键k1,led点亮,双击k1,led闪烁,长按k1,...

Global site tag (gtag.js) - Google Analytics