Cod sursa(job #1141645)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 13 martie 2014 00:18:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.97 kb
/** Z - algorithm **/
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int NMax = 2000010, MMax = 2000010;
int n, m, sol;
char A[NMax], B[MMax];
int Z[NMax];
int dp[MMax];
vector <int> ans;
// Z[i] = lungimea celui mai lung prefix al lui A care incepe pe pozitia i
// dp[i] = lungimea celui mai lung prefix al lui A care incepe in B pe pozitia i

void Read()
{
    ifstream f("strmatch.in");
    f>>(A + 1);
    f>>(B + 1);
    f.close();
}

void CreateZ()
{
    n = strlen(A + 1);
    m = strlen(B + 1);
    Z[1] = 0;
    for (int i = 2, j = 1; i<=n && A[i] == A[j]; ++i, ++j, ++Z[2]);
    int maxim, position;
    maxim = 2 + Z[2] - 1;
    position = 2;
    for (int i = 3; i <= n; ++i)
    {
        if (maxim < i)
        {
            int st, dr;
            for (st = 1, dr = i; dr <= n && A[st] == A[dr]; ++st, ++dr, ++Z[i]);
            maxim = i + Z[i] - 1;
            position = i;
        }
        else
        {
            int iprim = i - position + 1;
            if (i + Z[iprim] - 1 < maxim)
                Z[i] = Z[iprim];
            else
            {
                Z[i] = maxim - i + 1;
                int st, dr;
                for (st = maxim - i + 1 + 1, dr = maxim + 1; dr <= n && A[st] == A[dr]; ++st, ++dr, ++Z[i]);
                maxim = i + Z[i] - 1;
                position = i;
            }
        }
    }
}

void CreateDP()
{
    int maxim, position;
    for (int i = 1; i<=m && A[i] == B[i]; ++i, ++dp[1]);
    maxim = 1 + dp[1] - 1;
    if (dp[1] == n)
    {
        ++sol;
        ans.push_back(1);
    }
    position = 1;
    for (int i = 2; i <= m; ++i)
    {
        if (maxim < i)
        {
            int st, dr;
            for (st = 1, dr = i; st <= n && dr <= m && A[st] == B[dr]; ++st, ++dr, ++dp[i]);
            maxim = i + dp[i] - 1;
            position = i;
            if (dp[i] == n)
            {
                ++sol;
                if (ans.size() < 1000) ans.push_back(i);
            }
        }
        else
        {
            int iprim = i - position + 1;
            if (i + Z[iprim] - 1 < maxim)
                dp[i] = Z[iprim];
            else
            {
                dp[i] = maxim - i + 1;
                int st, dr;
                for (st = maxim - i + 1 + 1, dr = maxim + 1; st <= n && dr <= m && A[st] == B[dr]; ++st, ++dr, ++dp[i]);
                maxim = i + dp[i] - 1;
                position = i;
                if (dp[i] == n)
                {
                    ++sol;
                    if (ans.size() < 1000) ans.push_back(i);
                }
            }
        }
    }
}

void Write()
{
    ofstream g("strmatch.out");
    g<<sol<<"\n";
    for (vector <int> :: iterator it = ans.begin(); it != ans.end(); ++it)
        g<<*it - 1<<" ";
    g<<"\n";
    g.close();
}

int main()
{
    Read();
    CreateZ();
    CreateDP();
    Write();
    return 0;
}