Cod sursa(job #1291235)

Utilizator 2dorTudor Ciurca 2dor Data 12 decembrie 2014 16:32:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int MAXC = 4000006;

string Pattern, Text, S;
int z[MAXC];
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) {
            if (S[0] != S[k]) continue;
            Left = Right = k;
            for (int i = 0; S[i] == S[Right]; ++i)
                ++Right;
            --Right;
            z[k] = Right - Left + 1;
        }else {
            if (z[k - Left] < Right - k + 1) {
                z[k] = z[k - Left];
            }else {
                for (int i = Right - k; S[i] == S[Right]; ++i)
                    ++Right;
                --Right;
                Left = k;
                z[k] = Right - Left + 1;
            }
        }
    }
    for (int i = PatternLength; i < SLength; ++i) {
        if (z[i] >= PatternLength) {
            Solution.push_back(i - PatternLength);
        }
    }
    fout << Solution.size() << '\n';
    for (int i = 0; i < min(1000, (int)Solution.size()); ++i) {
        fout << Solution[i] << ' ';
    }
    fin.close();
    fout.close();
    return 0;
}