SlovingReport(2.2)

1282

Posted by SixTeen on October 24, 2015

#1282


###Soj-1282

p

这题是字符串匹配问题,用了kmp算法

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

int nextarray[1000000];
int pattern[1000000];
int target[1000000];

void setNextarray(int n){
    nextarray[0] = 0;
    int k = 0;
    for (int i = 1; i < n; i++){
        k = nextarray[i-1];
        while (pattern[i] != pattern[k] && k != 0){
            k = nextarray[k - 1];
        }
        if (pattern[i] == pattern[k]){
            nextarray[i] = k + 1;
        }
        else{
            nextarray[i] = 0;
        }
    }
}

void kmp(int m,int n){
    setNextarray(n);
    int i = 0;
    int k = 0;
    int pos = 0;
    while (i < m){
        while (pattern[pos] == target[i + k]){
            pos++;
            k++;
            if (k == n){
                cout << i << endl;
                return;
            }
        }
        if (k != 0){
            i = i + (k - nextarray[k - 1]);
            k = nextarray[k - 1];
            pos = k;
        }
        else{
            i++;
            k = 0;
            pos = 0;
        }
    }
    cout << "no solution" << endl;
}
int main(){
    int n;
    int m;
    while (scanf("%d", &n) != EOF){
        for (int i = 0; i < n; i++){
            cin >> pattern[i];
        }
        cin >> m;
        for (int i = 0; i < m; i++){
            cin >> target[i];
        }
        kmp(m,n);
    }
    return 0;
}