-
Archives
- January 2012
- December 2011
- August 2011
- July 2011
- June 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009
- December 2008
- November 2008
- October 2008
- September 2008
- August 2008
- July 2008
- June 2008
-
Meta
Tag Archives: 字符串问题
URAL 1486 —— Equal Squares
题目在这里： http://acm.timus.ru/problem.aspx?space=1&num=1486 第一行读入2个整数n,m(1
URAL 1769 —— Old Ural Legend
一个全部是由数字组成的字符串，问求最小的一个正数，该数不能是该串的子串。
ZOJ 1953 —— Advanced Fruits
题意：两名字组合出包含它们的最短串 典型的DP，典型的规划方程 /* d[i][j] 代表第一个串显示i位，第二个串显示j位，得到的和串 d[0][j] = s2[0~j - 1]，d[i][0] =s1[0][i-1] d[i][j] = d[i-1][j-1] + 1(1表示一个字符) :s1[i-1] == s2[j-1] d[i][j] = min(d[i-1][j],d[i][j-1]) + 1 :s1[i-1] != s2[j-1] */
HDU 2846 —— Repository
对查询串建立 trie 树，记录每个节点是否是结尾，然后对输入的物品串进行搜索。 直接 strstr 也可以吧。
POJ grids 2744 —— 子串
现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串x，使得对于已经给出的字符串中的任意一个y，x或者是y的子串，或者x中的字符反序之后得到的新字符串是y的子串。 我先把第一个字符串的所有后缀串生成，然后和剩下的 n-1 个字符串逐个用 KMP 匹配。源字符串匹配后，就需要反转源字符串，而不是子串。
POJ 3450 —— Corporate Identity
给定多个字符串，求最长的公共连续子串。 http://hi.baidu.com/superlong/blog/item/9bd8564397a9c31b9213c622.html http://hi.baidu.com/lewutian/blog/item/489b52fd0dda5b4ed7887d5f.html http://blog.sina.com.cn/s/blog_6635898a0100l4gh.html http://www.chenyajun.com/2010/04/11/4749
SGU 170 —— Particles
http://d.ream.at/sgu-170/ 两个串都是由 + 和 - 构成，如果一个串的相邻字符不同，则它们可以交换，问是否可以将一个串通过交换变换为另外一个串？ 如果是 +，则为 1，否则是 0。 找到一对不同且各自与目标串相反的位，异或一下0……010……010……，然后再找，一直找到最后，如果源串不能变成目标串，那就无解。
SGU 142 —— Keyword
有一个长字符串由 2 种字符 a 和 b 组成，求一个这样的子串：它只包含 a 和 b，它不是长字符串的子串，问其最短长度是多少？ 由于字符串只含有 2 种字符，故可以转换为位操作。
POJ 1035 —— Spell checker
http://hi.baidu.com/billdu/blog/item/0060c4c54bf583c539db4928.html 你是一个新开发的“魔法检验系统”程序的程序员。现在系统中的一个模块由你开发。首先，数据中给了你一本字典，以“#”结束，单词数不超过10000个，单词的长度不超过15个字符，且均由小写字母组成。之后给了你一些待检验的单词，你需要按照以下规则检查单词。 一、如果单词在字典中出现过，输出“xxx is correct”。 二、如果不然，先输出“xxx:”，然后输出可能的正确单词。 （如果没有可能的正确单词，你必须在冒号后面直接输出回车。） 三、“可能的正确单词”必须满足：在原单词上添加、替换或者删除一个字符之后成为词典中的单词。 直接硬搞。
POJ 3729 —— Facer’s string
给你两个数字串 S1 和 S2，求 S1 中有多少个长度等于 K 的子串在 S2 中能找到。而没有长度大于 K 的 S1 的子串出线在 S2 中。 思路：后缀数组。