Cod sursa(job #908008)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 8 martie 2013 17:18:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
#define N 4000010
using namespace std;

int i, j, n, m, L, R, k, Z[N];
string A, B;

int main()
{
    ifstream fi("strmatch.in");
    ofstream fo("strmatch.out");
    fi >> A >> B;
    m = A.length();
    A = A + "#" + B + "#";
    n = A.length(); n--;
    L = R = 0;
    for(i = 1; i < n; i++)
    if(R <= i)
    {
        L = R = i;
        while(R < n and A[R] == A[R-i]) R++;
        Z[i] = R - i; R--;
    } else
    {
        j = i - L;
        if(Z[j] < R - i + 1)
        {
            Z[i] = Z[j];
            continue;
        }
        L = i;
        while(R < n and A[R] == A[R-i]) R++;
        Z[i] = R - i; R--;
    }
    for(i = 1; i < n; i++) if(Z[i] == m) k++;
    fo << k << "\n";
    for(i = 1; i < n; i++) if(Z[i] == m) fo << i - m - 1 << " ";
    return 0;
}