Cod sursa(job #1099519)

Utilizator a96tudorAvram Tudor a96tudor Data 5 februarie 2014 21:42:19
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define MAX 1000
#define N_MAX 2000010
#define pb push_back
using namespace std;
int Urm[N_MAX],n,m;
char A[N_MAX],B[N_MAX];
vector <int> Sol;
inline void Write_Data()
{
    printf("%d\n",Sol.size());
    for (vector <int> :: iterator it=Sol.begin();it!=Sol.end();++it)
        printf("%d ",*it);
    printf("\n");
}
inline void Next(char B[N_MAX],int m)
{
    int k=-1;
    Urm[0]=0;
    for (int i=1;i<m;++i)
    {
        while (k>-1 && B[k+1]!=B[i]) k=Urm[k];
        if (B[k+1]==B[i]) k++;
        Urm[i]=k;
    }
}
inline void Solve(char A[N_MAX],char B[N_MAX],int n,int m)
{
    int k=-1;
    for (int i=0;i<n;++i)
    {
        while (k>-1 && B[k+1]!=A[i]) k=Urm[k];
        if (B[k+1]==A[i]) k++;
        if (k==m-1)
            {
                if (Sol.size()<MAX) Sol.pb(i-m+1);
                k=Urm[k];
            }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(B), gets(A);
    n=strlen(A), m=strlen(B);
    Next(B,m);
    Solve(A,B,n,m);
    Write_Data();
    fclose(stdin), fclose(stdout);
    return 0;
}