ip攻击

给你1亿个ip地址和每个ip访问的时间(00:00:00= <时间 <=23:59:59，并且已经按照时间排好序了)，然后给定一段时间X，定义在X内如果某IP的访问次数超过Y次，则判定该IP为攻击IP。要求输出所有攻击IP。只有一组测试用例。第一行输入IP记录数(即10万)，时间X(10= 输入示例：(为了方便，只给出8个，意思意思)
8 10 2
10.254.82.126 00:00:39
10.85.124.135 00:00:40
10.254.82.126 00:00:44
10.254.82.126 00:00:44
10.1.82.125 00:00:45
10.85.124.135 00:00:48
10.254.82.126 00:00:48
10.254.82.126 00:00:49
输出示例：
10.254.82.126
10.85.124.135

 

 

   一看又是字符串匹配的问题,hash喽....这里说明下,我最近练习伪码的写法,所以都没有具体的代码,但是我会很详细的描述思路,如果看了不会写代码,加上你又十万火急的需要代码的话,可以联系我!!!要酬劳的哦,just joking!!! absolutely free^_^

   我先分析如下  

1.读文件的问题

  这里 fscanf(fp,"%s %s",ip_str, time_str)

      ip_str = 10.254.82.126;

    time_str = 00:00:39;

    time_str再分成m, h,　ｓ就是

　　 sscanf(ip_str,"%d:%d:%d",&h,&m,&s);

 一步到位:

fscanf(fp,"%s %d:%d:%d",ip_str, &hour, &minute, &second)

 

2.hash这个说过无数次了,你不会我也没办法自己去学

  HASH,add_hash

  我这里也许好需要一个delete_hash

  typedef struct hash

   {

 

    char IP[IP_MAX_LEN];

    int count;

    int times;

    struct hash* next;

   }HASH;

  需要注意的是这里的times是需要更新的

  10.254.82.126 00:00:39
  10.85.124.135 00:00:40 
  10.254.82.126 00:00:33  

  10.254.82.126 00:00:44

  如果这里你刚好是x=2你不更新就有问题了... 

3.选取合适的hash函数之后我们就可以开始了...

  方法一是:

    while(fscanf(......)!=EOF)

     {

       .....

       add_hash(ip_str, times);

     }  
 

    add_hash(char* ip_str,uint times)

     {

      count++//与ip_str相同的list里的节点都加1

      add_list_tail;

      //我这里是添加到尾,方便每次取最早的那个,以及删除

      这里如果存在 时间小于Y话 count又是==x

       就可以打印ip了    

  

      if(时间差不大于y)

        delete_early_hash()

       //删除最早的那个，与这个删除的节点相同的都需要--

      }

    这个是个比较繁琐的,1亿的数字,理论上这个是可行的,可一旦不同的ip过多,hash又不好的话,很有可能变hash为list

 

 

方法二:

   1.从第一行数据开始取的所有x时间内的数据,假设共有x_line行

      对这个x_line行做hash 

      add_hash原则相同就是

         相同的ip的所有count+1

      如果这x_line内有count=y的话,就打印了..一旦打印了为了防止一直打印这个数,可以把打印了的count--

    

     10.254.82.120 00:00:29 
     10.85.124.135 00:00:30 
     10.254.82.126 00:00:33  

     10.254.82.126 00:00:34

     10.85.124.135 00:00:35 
     

     x=5, y=2

     这样

      10.254.82.120 00:00:29 
      10.85.124.135 00:00:30 
      10.254.82.126 00:00:33  

      10.254.82.126 00:00:34

      打印10.254.82.126

   

    这样

     10.85.124.135 00:00:30 
     10.254.82.126 00:00:33  

     10.254.82.126 00:00:34

     10.85.124.135 00:00:35 
     也打印10.254.82.126

     

    

   2.再取x_line+1行的时候,第一行的数据就可以delete了,将这个   

     x_line+1的数据也好处理,之前的结构还可以用!直到取到某行的时间大于第二行的数据+x,数据内的操作如上.

   3.如此重复下去.

     

   好了说的我自己都快糊涂了,这个题目2小时搞定都有点悬....大致思路如此还有很多需要考虑的