Cod sursa(job #1099572)

Utilizator a96tudorAvram Tudor a96tudor Data 5 februarie 2014 22:43:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
#define N_MAX 2000010
#define MAX 1000
using namespace std;
int N,M,Pr[N_MAX];
char A[N_MAX],B[N_MAX];
vector <int> Sol;
inline void Write_Data()
{
    int N=Sol.size();
    N=min(N,MAX);
    printf("%d\n",Sol.size());
    for (int i=0;i<N;++i)
        printf("%d ",Sol[i]);
    printf("\n");
}
inline void Solve(int N,int M)
{
    int k=0;
    for (int i=1;i<=M;++i)
    {
        while (k>0 && B[i]!=A[k+1]) k=Pr[k];
        if (B[i]==A[k+1]) k++;
        if (k==N) Sol.pb(i-N);
    }
}
inline void Gen_Pr(int N)
{
    int k=0;
    Pr[1]=0, Pr[0]=0;
    for (int i=2;i<=N;++i)
    {
        while (k>0 && A[i]!=A[k+1]) k=Pr[k];
        if (A[i]==A[k+1]) k++;
        Pr[i]=k;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(A+1), gets(B+1);
    A[0]=' ', B[0]=' ';
    N=strlen(A)-1, M=strlen(B)-1;
    Gen_Pr(N);
    Solve(N,M);
    Write_Data();
    fclose(stdin);
    fclose(stdout);
}