Cod sursa(job #1301631)

Utilizator danalex97Dan H Alexandru danalex97 Data 26 decembrie 2014 11:31:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 2000010;

ifstream F("strmatch.in");
ofstream G("strmatch.out");

int n,m,pi[N];
char a[N],b[N];

void build(char a[],int n)
{
    int p = 0;
    for (int i=2;i<=n;++i)
    {
        while ( p > 0 && a[i] != a[p+1] )
            p = pi[p];
        if ( a[i] == a[p+1] )
            p++;
        pi[i] = p;
    }
}

vector<int> match(char a[],int n,char b[],int m)
{
    vector<int> ans;
    int p = 0;
    for (int i=1;i<=m;++i)
    {
        while ( p > 0 && b[i] != a[p+1] )
            p = pi[p];
        if ( b[i] == a[p+1] )
            p++;
        if ( p == n )
            ans.push_back(i-n);
    }
    return ans;
}

int main()
{
    F>>(a+1)>>(b+1);
    n = strlen(a+1);
    m = strlen(b+1);

    build(a,n);
    vector<int> ans = match(a,n,b,m);

    G<<ans.size()<<'\n';
    for (int i=0;i<int(ans.size()) && i<1000;++i)
        G<<ans[i]<<' ';
    G<<'\n';
}