Cod sursa(job #1980855)

Utilizator petrasromanPetras Roman petrasroman Data 14 mai 2017 10:53:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000000+3],c[2000000+3];
int A,C,v[2000000+3],ok;
vector <int> results;
vector <int> resultsok;
void prefix_c(int n)
{
    v[0]=-1;
    for(int i=2,j=0;i<=n;v[i++]=++j)
    {
        while(j>=0&&c[i]!=c[j+1])
        j=v[j];
    }
}
void KMP(int n, int m)
{
    int k=0;
    for(int i=1,j=0;i<=n;i++,j++)
    {
        while(j>=0&&a[i]!=c[j+1])
        j=v[j];
        if(j+1==m)
        {
            k++;
            results.push_back(i-m);
        }
    }
    g<<k<<'\n';
    for(int i=0;i<k;i++)
    g<<results[i]<<" ";
}
int main()
{
    f>>(c+1)>>(a+1);
    A=strlen(a+1);
    C=strlen(c+1);
    prefix_c(C);
    KMP(A,C);
    return 0;
}