Cod sursa(job #332901)

Utilizator levap1506Gutu Pavel levap1506 Data 20 iulie 2009 21:54:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <string>
#include <iostream>
#define maxn 2000000
using namespace std;
int pi[maxn], i, j, poz[1100];
string a,b;
int main()
{
    ifstream in;
    ofstream out;
    in.open("strmatch.in");
    out.open("strmatch.out");
    in >> a >> b;
    int N=a.length();
    int M=b.length();
    pi[0]=0;
    j=0;
    for (i=1;i<N;i++) {
        while (j>0&&a[j]!=a[i]) j=pi[j-1];
        if (a[j]==a[i]) j++;
        pi[i]=j;
    }
    j=0;
    for (i=0;i<M;i++) {
        while (j>0&&a[j]!=b[i]) j=pi[j-1];
        if (a[j]==b[i]) j++;
        if (j==N)
          if (poz[0]>1000) ++poz[0]; else poz[++poz[0]]=i-N+1;
    }
    out << poz[0] << "\n";
    for (i=1;i<=min(1000,poz[0]);i++) {
        out << poz[i] << " ";
    }
    out.close();
    return 0;
}