Pagini recente » Cod sursa (job #372692) | Cod sursa (job #1775334) | Cod sursa (job #3256329) | Cod sursa (job #1176607) | Cod sursa (job #1061930)
#include<fstream>
#include<iostream>
#include<string.h>
using namespace std;
char a[2000005],b[2000005];
int n,m,q,pi[2000005],pos[1010],sol;
void citire() {
ifstream in("strmatch.in");
int i;
in.getline(a,2000001);
in.getline(b,2000001);
for(i=0;a[i]<='z'&&a[i]>='0';i++);
m=i;
for(i=0;b[i]<='z'&&b[i]>='0';i++);
n=i;
for(i=m;i>=1;i--)
a[i]=a[i-1];
for(i=n;i>=1;i--)
b[i]=b[i-1];
a[0]=b[0]=' ';
in.close();
}
void prefix() {
int i;
for(i=2,pi[1]=0;i<=m;i++) {
while(q&&a[q+1]!=a[i])
q=pi[q];
if (a[q+1]==a[i])
++q;
pi[i] = q;
}
}
void solve() {
int i;
for (i=1;i<=n;i++) {
while (q && a[q+1] != b[i])
q = pi[q];
if (a[q+1] == b[i])
++q;
if (q == m)
{
q = pi[m];
++sol;
if (sol <= 1000)
pos[sol] = i-m;
}
}
}
void afisare() {
ofstream out("strmatch.out");
int i;
out<<sol<<'\n';
if(sol>1000)
sol=1000;
for(i=1;i<=sol;i++)
out<<pos[i]<<" ";
out<<'\n';
out.close();
}
int main() {
citire();
prefix();
solve();
afisare();
return 0;
}