Mudanjiang2014-First-Round-I.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <cassert>
#include <cctype>
using namespace std;

typedef long long LL;
typedef long long ULL;

const ULL MAGIC = 61;
const int N = 100005;

ULL power[N];
int n , m;
char str[4][N] , t[N];
ULL hash[8][N] , hasht[N];
int f[8][N];
void init() {
    power[0] = 1;
    for (int i = 1 ; i < N ; ++ i)
        power[i] = power[i - 1] * MAGIC;
}

inline ULL get(ULL *H , int l , int r) {
    return H[r] - H[l - 1] * power[r - l + 1];
}

void print(int i , int j) {
    int x = (j / 2) * n;

    if (f[j][i]) {
        print(f[j][i] % (m + 1) , f[j][i] / (m + 1));
        if (j & 1) {
            for (int k = n ; k > 0 ; -- k)
                printf("%d " , x + k);
        } else {
            for (int k = 1 ; k <= n ; ++ k)
                printf("%d " , x + k);
        }
    } else {
        //printf("%d %d\n" , i , j);
        if (j & 1) {
            for (int k = i ; k > 0 ; -- k)
                printf("%d " , x + k);
        } else {
            for (int k = n - i + 1 ; k <= n ; ++ k)
                printf("%d " , x + k);
        }
    }
}

void work() {
    int i , j , k , x , y;
    scanf("%d%d",&n,&m);
    for (i = 0 ; i < 4 ; ++ i) {
        scanf("%s" , str[i] + 1);
        for (j = 1 ; j <= n ; ++ j)
            hash[i << 1][j] = hash[i << 1][j - 1] * MAGIC + (str[i][j] - 'a' + 1);
        for (j = 1 ; j <= n ; ++ j)
            hash[i << 1 | 1][j] = hash[i << 1 | 1][j - 1] * MAGIC + (str[i][n - j + 1] - 'a' + 1);
    }
    scanf("%s" , t + 1);
    for (j = 1 ; j <= m ; ++ j)
        hasht[j] = hasht[j - 1] * MAGIC + (t[j] - 'a' + 1);
    if (m <= n) {
        bool flag = 0;
        for (i = 0 ; i < 8 && !flag ; ++ i)
            for (j = 1 ; j + m - 1 <= n && !flag ; ++ j)
                if (get(hash[i] , j , j + m - 1) == hasht[m])
                    flag = 1 , x = i , y = j;
        if (flag) {
            if (x & 1) {
                j = (x / 2) * n + y + m - 1;
                for (i = j ; i > j - m ; -- i) {
                    printf("%d " , i);
                }
                puts("");
            } else {
                j = (x / 2) * n + y;
                for (i = j ; i < j + m ; ++ i) {
                    printf("%d " , i);
                }
                puts("");
            }
            return;
        }
    }

    memset(f , -1 , sizeof(f));
    for (i = 0 ; i < m ; ++ i) {
        if (i && i <= n) {
            for (j = 0 ; j < 8 ; ++ j) {
                if (hasht[i] == get(hash[j] , n - i + 1 , n)) {
                    f[j][i] = 0;
                }
            }
        }

        for (j = 0 ; j < 8 ; ++ j) {
            if (!~f[j][i]) continue;
            for (k = 0 ; k < 8 ; ++ k) {
                if ((j ^ k) == 1) continue;
                if (get(hasht , i + 1 , m) == get(hash[k] , 1 , m - i)) {
                    print(i , j);
                    //
                    x = (k >> 1) * n;
                    if (~k & 1) {
                        for (int l = 1 ; l <= m - i ; ++ l)
                            printf("%d " , x + l);
                    } else {
                        for (int l = n ; l >= n - (m - i) + 1 ; -- l)
                            printf("%d " , x + l);
                    }
                    puts("");
                    return;
                }
            }
            if (i + n <= m) {
                for (k = 0 ; k < 8 ; ++ k) {
                    if ((j ^ k) == 1) continue;
                    if (get(hasht , i + 1 , i + n) == hash[k][n]) {
                        f[k][i + n] = j * (m + 1) + i;
                    }
                }
            }
        }
    }
    for (i = 0 ; i < 8 ; ++ i)
        if (~f[i][m]) {
            print(m , i);
            puts("");
            return;
        }
    puts("No solution!");
}

int main() {
    init();
    int _; scanf("%d",&_); while (_--)
        work();
    return 0;
}