Cod sursa(job #1647349)

Utilizator sebinechitasebi nechita sebinechita Data 10 martie 2016 20:08:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAX 2000010

char a[MAX], b[MAX];
int pi[MAX];

vector <int> v;

void fi(char c[], int n, int pi[])
{
    int k;
    pi[1] = 0;
    for(int i = 2 ; i <= n ; i++)
    {
        k = pi[i - 1];

        while(k && c[i] != c[k + 1])
            k = pi[k];

        if(c[i] == c[k + 1])
        {
            k++;
        }

        pi[i] = k;
    }
}

int main()
{
    int n, m, i, dr = 0, j;
    fin >> a + 1;
    fin >> b + 1;
    n = strlen(a + 1);
    m = strlen(b + 1);
    fi(a, n, pi);
    j = 0;
    for(i = 1 ; i <= m ; i++)
    {
        while(j && a[j + 1] != b[i])
            j = pi[j];
        if(a[j + 1] == b[i])
            j++;
        if(j == n)
        {
            ++dr;
            if(dr <= 1000)
                v.push_back(i - n);
        }
    }
    fout << dr << "\n";
    for(j = 0 ; j < v.size() ; j++)
        fout << v[j] << " ";
}