Pagini recente » Cod sursa (job #2117552) | Cod sursa (job #1751186) | Cod sursa (job #1871259) | Cod sursa (job #1363297) | Cod sursa (job #332847)
Cod sursa(job #332847)
#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++) {
if (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++) {
if (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;
}