Cod sursa(job #1524123)

Utilizator kiunyAndrei Gavrila kiuny Data 13 noiembrie 2015 16:14:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string pat, s;
vector <int> p;
int l, n;
void prefix()
{

    int k = -1;
    p[0] = k;
    int i = 0;
    while(i < l)
    {
        while(k >= 0 && pat[i] != pat[k]) k = p[k];
        k++;
        i++;
        p[i] = k;
    }
}

vector <int> matches;

void getMatches()
{
    int j = 0;
    int i = 0;
    while(i < n)
    {
        while( j >= 0 && s[i] != pat[j])
        {
            j = p[j];
        }
        j++;
        i++;
        if( j == l)
        {
            matches.push_back(i-j);
            j = p[j];
        }
    }
}

int main()
{
    cin >> pat;
    cin >> s;
    l = pat.length();
    n = s.length();
    p.resize(l+1, 0);
    prefix();
    getMatches();
    cout << matches.size() << '\n';
    for(int i = 0; i < matches.size(); i++)
    {
        if(i > 1000)
            break;
        cout << matches[i] << ' ';

    }
}