Cod sursa(job #1090706)

Utilizator kiralalaChitoraga Dumitru kiralala Data 22 ianuarie 2014 23:12:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005

using namespace std;
//CU KMP
FILE* f=freopen("strmatch.in","r",stdin);
FILE* o=freopen("strmatch.out","w",stdout);

char str[NMAX],sub[NMAX];
int n,m,num;
int pad[NMAX];
queue<int> sol;

void Reading()
{
    scanf("%s\n%s",sub,str);
    n=strlen(str);
    m=strlen(sub);
    sub[m]='#';
}
void InitPad()
{
    pad[0]=-1;
    for(int i=2;i<=m;++i)
        if(sub[pad[i-1]]==sub[i-1])
            pad[i]=pad[i-1]+1;
}

int main()
{
    Reading();

    if(m>n) { printf("0"); return 0; }
    InitPad();

    int k=0;
    for(int i=0;k+i<n;)
    {
        if(str[k+i]==sub[i]) {
            if(i==m-1)
                { num+=1; if(num<1000) sol.push(k); }
            i+=1;
        }
        else {
            k+=i-pad[i];
            i=(pad[i]>-1)?pad[i]:0;
        }
    }

    printf("%d\n",num);
    while(!sol.empty()) { printf("%d ",sol.front()); sol.pop(); }

    return 0;
}