Cod sursa(job #2035877)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 9 octombrie 2017 21:51:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

vector<int> sol;

void NSN(char *x, int m, char *y, int n)
{
    int j, k, ell;

    /* Preprocessing */
    if (x[0] == x[1])
    {
        k = 2;
        ell = 1;
    }
    else
    {
        k = 1;
        ell = 2;
    }

    /* Searching */
    j = 0;
    while (j <= n - m)
        if (x[1] != y[j + 1])
            j += k;
        else
        {
            if (memcmp(x + 2, y + j + 2, m - 2) == 0 &&
                    x[0] == y[j])
                sol.push_back(j);
            j += ell;
        }
}

char x[2000005], y[2000005];

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s", x, y);
    NSN(x, strlen(x), y, strlen(y));
    printf("%d\n", sol.size());
    for(int i = 0; i < sol.size(); i++)
        printf("%d ", sol[i]);
    return 0;
}