Cod sursa(job #1951851)

Utilizator matystroiaStroia Matei matystroia Data 3 aprilie 2017 20:27:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int N=2e6;

int n, m, pre[N];
char a[N], b[N];
vector<int> ans;

void build_prefix()
{
    int j=0;
    for(int i=1;i<n;++i)
    {
        while(j>0&&a[j]!=a[i])
            j=pre[j-1];
        if(a[i]==a[j])
            j++;
        pre[i]=j;
    }
}

void find_matches()
{
    int j=0;
    for(int i=0;i<m;++i)
    {
        while(j>0&&a[j]!=b[i])
            j=pre[j-1];
        if(a[j]==b[i])
            j++;
        if(j==n)
            ans.push_back(i-n);
    }
}

int main()
{
    fin>>a>>b;
    n=strlen(a), m=strlen(b);

    build_prefix();
    find_matches();

    fout<<ans.size()<<'\n';
    for(int p:ans)
        fout<<p+1<<" ";

    return 0;
}