Cod sursa(job #1290146)

Utilizator 2dorTudor Ciurca 2dor Data 10 decembrie 2014 21:15:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MAXN = 2000005;
string Pattern, Text, S;
int z[MAXN];
int Left, Right;
vector<int> Solution;

int main() {
    fin >> Pattern >> Text;
    S = Pattern + Text;
    int SLength = S.size();
    int PatternLength = Pattern.size();
    for (int k = 1; k < SLength; ++k) {
        if (Right < k) {//we're outside of the Z-box
            if (S[0] == S[k]) {//first letters equal
                Left = Right = k;
                for (int i = 0; S[i] == S[Right]; ++i)
                    ++Right;
                --Right;
                z[k] = Right - k + 1;
            }
        }else {//inside the Z-box
            /*if the length of the Z-box starting at
            (k - Left + 1) (aka the position of letter k in the Pattern)
            is STRICTLY smaller than the current Z-box (between Left and Right)
            then we can use the information as we know we cannot go any further
            with the comparisons
            */
            if (z[k - Left] < Right - k + 1) {
                z[k] = z[k - Left];
            }else {
            //here we know we might find merged strings, so we
            //go on with the comparisons beyond Right, actually extending out Z-box
                //0 1 2 3 4 5 6 7 8 9 10 11 12 13
                //A B A C A B B C A B  A  B  A  B
                int q = Right;
                for (int i = Right - k; S[i] == S[q]; ++i) {
                    ++q;
                }
                Left = k;
                Right = q - 1;
                z[k] = q - k;
            }
        }
    }
    /*for (int i = 0; i < SLength; ++i) {
        fout << S[i] << ' ' << i << ' ' << z[i] << '\n';
    }*/
    for (int i = PatternLength; i < SLength; ++i) {
        if (z[i] >= PatternLength) {
            Solution.push_back(i - PatternLength);
        }
    }
    fout << Solution.size() << '\n';
    int SolutionSize = Solution.size();
    for (int i = 0; i < SolutionSize; ++i)
        fout << Solution[i] << ' ';

    fin.close();
    fout.close();
    return 0;
}