Cod sursa(job #1289904)

Utilizator 2dorTudor Ciurca 2dor Data 10 decembrie 2014 15:28:44
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 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
            if (z[k - Left] >= Right - k + 1) {
                //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 + 1;
                for (int i = z[Right - Left]; S[i] == S[q]; ++i) {
                    ++q;
                }
                z[k] = q - k;
            }
        }
    }

    /*for (int i = 0; i < SLength; ++i) {
        cerr << z[i] << ' ';
    }*/

    for (int i = PatternLength; i < SLength; ++i)
        if (z[i] == PatternLength)
            Solution.push_back(i - PatternLength);

    fout << Solution.size() << '\n';
    for (size_t i = 0; i < Solution.size(); ++i)
        fout << Solution[i] << ' ';

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