算法问题，如何计算子字符串在那个位置最为集中？

Question

本帖最后由 lwp1493 于 2009-10-09 10:18:07 编辑

Answer 1

  .+++..........+.+.+.+.+......................++.++....
A  ---          ---------                      -----
B  ----------------------                      -----
C  ---          - - - - -                      -- --
最好先给“集中”明确定义。
比如例子中的3种分组法，得到的“最集中”的答案各不相同。

Answer 2

        /// <summary>
        /// 查找字符串位置
        /// </summary>
        /// <param name="AllStr">文本</param>
        /// <param name="FindStr">所要查找的字符串</param>
        /// <returns>密集所在位置字符串</returns>
        public static string Display(string AllStr,string FindStr)
        {
            ArrayList al = new ArrayList();
            Regex reg = new Regex(FindStr);
            Match ma = reg.Match(AllStr);
            while (ma.Success)
            {
                ma = reg.Match(AllStr, ma.Index + ma.Length);
                al.Add(ma.Index+1);
            }
            int[] ResultArray=(int[])al.ToArray(typeof(int));
            Array.Sort(ResultArray);
            int tempResult = 0,DisCount = 1 ,FirstStrCount=0,FirstCount=0;
            ArrayList alcount = new ArrayList();
            for (int count = 0; count < ResultArray.Length-1; count++)
            {
                if (ResultArray[count] + FindStr.Length == ResultArray[count + 1])
                {
                    tempResult = ResultArray[count];
                    DisCount ++;
                }
                else
                {
                    if (DisCount <= 1 || DisCount<FirstCount)
                    {
                        DisCount = 0;
                    }
                    else
                    {
                        FirstCount = DisCount;
                        FirstStrCount = tempResult+FindStr.Length;
                        DisCount = 0;
                    }
                }
            }
            return Convert.ToString(FirstStrCount - FindStr.Length * FirstCount) + "～" + Convert.ToString(FirstStrCount + FindStr.Length);
        }
简单调用:
            string str = "“中国”一词最早出现是在周代《诗经》中，如《大雅•民劳》“惠此中国”。但《诗经》中的此类“中国中国中国中国中国中国中国中国中国中国”实为“国中”，还不是真正指国家。称国家的“中国”一词，在战国诸子百家的书中已屡见不鲜了。如《孟子•滕文公上》云：“陈良产地，悦周公仲尼之道，北学于中国”，又“兽蹄鸟迹之道，交于中国”；《庄子•田子方》：“中国之君子，明乎礼义而陋干知人心”……这些都说明：上古所谓“中国”，即指后世“中原”。但地域不及后世中原广，而相当于今山西、陕西、山东、河南、河北一带。中国中国中国中国中国中国　　“中国”一词的频繁使用，主要在周以后。《礼记•王制》有云：中国夷戎，五方之民，皆有性也……中国、蛮、夷、戎、狄，皆有安。”十分明显，此时的中国”一词，是与蛮、夷、戎、狄对举而使用的。如果说《礼记》的成书时间较靠后，则《左传•庄公三十一年》有凡诸侯有四夷之功，则献于王，王以警于夷。中国则否”的说法，足见春秋前期，中国”一词就已经与蛮、夷、戎、狄对举。那么中国”指谁呢 《公羊传•禧公四年》称：南夷与北狄交，中国不绝若线。桓公救中国而攘夷狄，卒荆，以此为王者之事也。”齐桓公救援邢国，卫国等国，被称作救中国”，足见此时的中国”，已经扩大到被认为是诸夏”的国家。";
            string input = "中国";            MessageBox.Show("字符串出现最多的位置是" + Display(str, input));

Answer 3

以上方法没有优化.建议使用泛型.
还有就是把下面这行删除了
//ArrayList alcount = new ArrayList();

Answer 4

string str = "“中国”一词最早出现是在周代《诗经》中，如《大雅?民劳》“惠此中国”。但《诗经》中的此类“中国”实为“国中”，还不是真正指国家。称国家的“中国”一词，在战国诸子百家的书中已屡见不鲜了。如《孟子?滕文公上》云：“陈良产地，悦周公仲尼之道，北学于中国”，又“兽蹄鸟迹之道，交于中国”；《庄子?田子方》：“中国之君子，明乎礼义而陋干知人心”……这些都说明：上古所谓“中国”，即指后世“中原”。但地域不及后世中原广，而相当于今山西、陕西、山东、河南、河北一带。中国中国中国“中国”一词的频繁使用，主要在周以后。《礼记?王制》有云：“中国夷戎，五方之民，皆有性也……中国、蛮、夷、戎、狄，皆有安。”十分明显，此时的“中国”一词，是与蛮、夷、戎、狄对举而使用的。如果说《礼记》的成书时间较靠后，则《左传?庄公三十一年》有“凡诸侯有四夷之功，则献于王，王以警于夷。中国则否”的说法，足见春秋前期，”中国”一词就已经与蛮、夷、戎、狄对举。那么“中国”指谁呢 《公羊传?禧公四年》称：“南夷与北狄交，中国不绝若线。桓公救中国而攘夷狄，卒荆，以此为王者之事也。”齐桓公救援邢国，卫国等国，被称作“救中国”，足见此时的”中国”，已经扩大到被认为是”诸夏”的国家。";
string input = "中国";
for(int i = 0;  i < str.Length; i ++)
{
int at = str.IndexOf(input, i);
if(at < 0) 
{
  break;
}
Console.Write(input + "@" + at);
i = at;
}

Answer 5

有这么复杂吗
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;namespace WindowsApplication82
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();            string str = "“中国”一词最早出现是在周代《诗经》中，如《大雅•民劳》“惠此中国”。但《诗经》中的此类“中国”实为“国中”，还不是真正指国家。称国家的“中国”一词，在战国诸子百家的书中已屡见不鲜了。如《孟子•滕文公上》云：“陈良产地，悦周公仲尼之道，北学于中国”，又“兽蹄鸟迹之道，交于中国”；《庄子•田子方》：“中国之君子，明乎礼义而陋干知人心”……这些都说明：上古所谓“中国”，即指后世“中原”。但地域不及后世中原广，而相当于今山西、陕西、山东、河南、河北一带。中国中国中国“中国”一词的频繁使用，主要在周以后。《礼记•王制》有云：“中国夷戎，五方之民，皆有性也……中国、蛮、夷、戎、狄，皆有安。”十分明显，此时的“中国”一词，是与蛮、夷、戎、狄对举而使用的。如果说《礼记》的成书时间较靠后，则《左传•庄公三十一年》有“凡诸侯有四夷之功，则献于王，王以警于夷。中国则否”的说法，足见春秋前期，”中国”一词就已经与蛮、夷、戎、狄对举。那么“中国”指谁呢 《公羊传•禧公四年》称：“南夷与北狄交，中国不绝若线。桓公救中国而攘夷狄，卒荆，以此为王者之事也。”齐桓公救援邢国，卫国等国，被称作“救中国”，足见此时的”中国”，已经扩大到被认为是”诸夏”的国家。";
            string input = "中国";            string Result = String.Empty;            while (str.IndexOf(Result + input) >= 0)
                Result += input;
            MessageBox.Show(Result);
        }
    }
}

Answer 6

再完善一下
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;namespace WindowsApplication82
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();            string str = "“中国”一词最早出现是在周代《诗经》中，如《大雅•民劳》“惠此中国”。但《诗经》中的此类“中国”实为“国中”，还不是真正指国家。称国家的“中国”一词，在战国诸子百家的书中已屡见不鲜了。如《孟子•滕文公上》云：“陈良产地，悦周公仲尼之道，北学于中国”，又“兽蹄鸟迹之道，交于中国”；《庄子•田子方》：“中国之君子，明乎礼义而陋干知人心”……这些都说明：上古所谓“中国”，即指后世“中原”。但地域不及后世中原广，而相当于今山西、陕西、山东、河南、河北一带。中国中国中国“中国”一词的频繁使用，主要在周以后。《礼记•王制》有云：“中国夷戎，五方之民，皆有性也……中国、蛮、夷、戎、狄，皆有安。”十分明显，此时的“中国”一词，是与蛮、夷、戎、狄对举而使用的。如果说《礼记》的成书时间较靠后，则《左传•庄公三十一年》有“凡诸侯有四夷之功，则献于王，王以警于夷。中国则否”的说法，足见春秋前期，”中国”一词就已经与蛮、夷、戎、狄对举。那么“中国”指谁呢 《公羊传•禧公四年》称：“南夷与北狄交，中国不绝若线。桓公救中国而攘夷狄，卒荆，以此为王者之事也。”齐桓公救援邢国，卫国等国，被称作“救中国”，足见此时的”中国”，已经扩大到被认为是”诸夏”的国家。";
            string input = "中国";            string Result = String.Empty;            while (str.IndexOf(Result + input) >= 0)
                Result += input;
            MessageBox.Show("最集中： "+Result+"位置： "+str.IndexOf(Result).ToString());
        }
    }
』

Answer 7

str中input字符串出现最频繁的位置；显然str中"中国中国中国"出现的次数最为频繁；那么如何通过程序得到这个位置？t得到什么位置？

Answer 8

结贴算了。9#的思想比较接近；而7#libinguest(风的足迹)和14# wartim(ilikeff8)的都曲解本意了（非连续的出现）感谢以上各位热心回答！