URAL 1423. String Tale

Author: 2015-11-17

ACM

, , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1423

1423. String Tale

Time limit: 1.0 second
Memory limit: 64 MB

Background

I want to tell you a story. Not entirely, but only the very beginning, because the ending of this story became a legend of programming—as well as its heroes.
When computers were large, when trees were small, when the sun shined brighter… Once upon a time there were Three Programmers. I doubt whether they participated in any programming contests, because there were no contests at that ancient time. There was neither ACM ICPC nor Timus Online Judge. But there were Three Programmers.

Problem

One day Three Programmers invented an amusing game to train memory and mental faculties. The First Programmer thought out a string S which was N characters long and passed it to the Second and the Third Programmers. The Second Programmer executed X (0 ≤ X < N) successive cycle shifts (a cycle shift is a transfer of the last character of the string to the beginning of this string) with this string. As a result of these operations a string T was produced, and the Second Programmer passed it to the Third Programmer. A task of the Third Programmer was to find the number X or make sure that the Second Programmer was mistaken, because the string T could not be produced from the string S via cycle shifts.

Input

The first line contains the integer number N (1 ≤ N ≤ 250000). The second line contains the string S. The third line contains the string T. Each string has length N and may contain any ASCII characters with codes from 33 to 255.

Output

If the string T can be produced from the string S via cycle shifts you should output the desired number X, otherwise you should output “−1”. If the problem has several solutions, you may output any of them.

Sample

input output 
11
abracadabra
racadabraab
 
9

Notes

Let us consider the strings S = “abracadabra” and T = “racadabraab”. The string T can be produced from the string S via 9 cycle shifts: “abracadabra” > “aabracadabr” > “raabracadab” > “braabracada” > “abraabracad” > “dabraabraca” > “adabraabrac” > “cadabraabra” > “acadabraabr” > “racadabraab”
Problem Author: Nikita Rybak, Ilya Grebnov, Dmitry Kovalioff
Problem Source: Timus Top Coders: First Challenge

2. 思路

给出两个字符串S和T，求T是否能够由S通过循环右移得到，如果可以，求循环右移的次数。

字符串匹配，使用KMP。将S复制一份拼接到S后面得到SS，用T去匹配SS。匹配成功则由匹配位置计算得到S循环右移的次数。

3. 代码

#include <cstdio>
#include <cstring>

const int MAX_LENGTH = 250001;

void solveP9d_StringTale();
int kmp(char target[], char pattern[], int table[]);
void buildTable(char pattern[], int table[]);

int main() {
    solveP9d_StringTale();
    return 0;
}

char target[MAX_LENGTH*2];
char pattern[MAX_LENGTH];
int table[MAX_LENGTH];
void solveP9d_StringTale() {
    int n;
    scanf("%d", &n);
    scanf("%s", target);
    scanf("%s", pattern);

    int targetLen = strlen(target);
    memcpy(target + targetLen, target, targetLen);
    target[targetLen + targetLen] = '\0';

    buildTable(pattern, table);
    int result = kmp(target, pattern, table);
    result = result > 0 ? (targetLen - result) : result;
    printf("%d\n", result);
}

int kmp(char target[], char pattern[], int table[]) {
    int m = 0, i = 0, targetLen = strlen(target), patternLen = strlen(pattern);

    while (m + i < targetLen) {
        if (pattern[i] == target[m + i]) {
            if (i == patternLen - 1) {
                return m;
            }
            ++i;
        } else {
            if (table[i] > -1) {
                m = m + i - table[i];
                i = table[i];
            } else {
                i = 0;
                ++m;
            }
        }
    }

    return -1;
}

void buildTable(char pattern[], int table[]) {
    int pos = 2, cnd = 0, len = strlen(pattern);
    table[0] = -1;
    table[1] = 0;

    while (pos < len) {
        if (pattern[pos - 1] == pattern[cnd]) {
            ++cnd;
            table[pos] = cnd;
            ++pos;
        } else if (cnd > 0) {
            cnd = table[cnd];
        } else {
            table[pos] = 0;
            ++pos;
        }
    }
}