欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

福州大学算法作业题 - 最长子串

程序员文章站 2022-04-24 18:33:37
★实验任务 ★数据输入 ★数据输出 ★数据范围 代码1: 代码2: 代码3: ......

★实验任务

给你一个长度为 n 的数组,现在需要求出异或和为零的最长连续子串。 一个子串的异或和指的是将子串中所有的数异或起来得到的值,比如给定 {1,1,2,2},异或和为零的连续子串有{1,1},{2,2},{1,1,2,2}。其中最长的连续 子串为{1,1,2,2}。 

★数据输入

输入数据占两行,第一行输入一个正整数 n,第二行输入 n 个非负整数,任 意两个数之间由空格隔开。 

★数据输出

输出三个整数 l、s、t 分别代表子串的长度以及子串的左右端点坐标(数组 下标从 1 开始),如果存在多解,则输出 s 值最小的解。 如果不存在这样的子串,则只需要输出一个-1。 

福州大学算法作业题 - 最长子串

★数据范围

50%的得分点,n<=100; 80%的得分点,n<=1000; 100%的得分点,n<=100000。 n 个整数取值范围在 int 范围内。

代码1:

#include <stdio.h>  
#include <map>  
using namespace std;    
int main(){  
    int n;  
    scanf("%d", &n);  
    int * a = new int[n];  
    int i;  
    for(i=0;i<n;i++){  
        scanf("%d", &a[i]);  
    }  
    map<int,int> m;  
    m[0] = -1;  
    map<int , int>::iterator ite;  
    int con = 0;  
    int l=-1,s=1,t=1;  
    int tl;  
    for(i=0;i<n;i++){  
        con^=a[i];  
        ite = m.find(con);   
        if( ite != m.end() ){  
            tl = i - ite->second;  
            if(tl > l){  
                l = tl;  
                s = ite->second+2;  
                t = i+1;  
            }  
        }else{  
            m[con] = i;  
        }  
    }  
    if(l == -1){  
        printf("%d", l);  
    }else{  
        printf("%d %d %d", l, s, t);  
    }  
    return 0;  
}  

 代码2:

#include<iostream>  
#include<cstdio>  
#include<map>  
using namespace std;  
  
map<int,int> tag;  
int num[100005];  
int main(){  
    int n,i,length,start,end;  
    start = end =-1;  
    length=-1;  
    tag[0]=0;  
    num[0]=0;  
    scanf("%d",&n);  
    for(i=1;i<=n;i++){  
        scanf("%d",&num[i]);  
        num[i]=num[i-1]^num[i];  
        if(tag.find(num[i])==tag.end()){  
            tag[num[i]]=i;  
        }  
        else{  
            if(i-tag[num[i]]>length){  
                length=i-tag[num[i]];  
                start=tag[num[i]]+1;  
                end=i;  
            }  
        }  
    }  
    if(length==-1){  
        printf("%d\n",-1);  
    }  
    else{  
        printf("%d %d %d\n",length,start,end);  
    }  
    return 0;  
}  

代码3:

#include<iostream>  
#include<map>  
#include<cstdio>  
using namespace std;  
int n, l=-1, s, e;  
int total = 0, tmp;  
map<int, int> m;  
  
int main(){  
    int i;  
    scanf("%d", &n);  
    for(i=1; i<=n; i++){  
        scanf("%d", &tmp);  
        total = total ^ tmp;  
        if(total == 0){  
            l = i; s = 1; e = i;  
        }  
        // 不为0就一直记录,为零单独考虑,存一个最开始total为0的节点   
        else{  
            if(m.find(total) == m.end())  
                m[total] = i;  
            else{  
                if(i - m[total] > l){  
                    l = i - m[total];  
                    s = m[total] + 1;  
                    e = i;  
                }  
            }   
        }  
    }  
    if(l > 0)  
        printf("%d %d %d\n", l, s, e);  
    else  
        printf("-1\n");  
    return 0;   
}