Pagini recente » Cod sursa (job #2607778) | Cod sursa (job #699055) | Cod sursa (job #2988922) | Cod sursa (job #768465) | Cod sursa (job #2976323)
#include<bits/stdc++.h>
using namespace std;
const int N = 2000009;
char a[N], b[N];
int t[N], p[N], ct;
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
// auto& in = cin;
// auto& out = cout;
void build()
{
int c = 0;
for(int i = 1; i<strlen(a); i++)
{
while(c && a[i] != a[c])
c = t[c-1];
if(a[i] == a[c])
c++;
t[i] = c;
}
}
void debug_t()
{
for(int i = 0; i<strlen(a); i++)
out<<t[i]<<' ';
out<<endl;
}
void show()
{
out<<ct<<endl;
for(int i=0;i<min(1000,ct);i++)
out<<p[i]<<' ';
out<<endl;
}
int main(){
in>>a>>b;
build();
// debug_t();
int j=0;
for(int i=0; i<strlen(b); i++)
{
// out<<"i: "<<i<<"; j: "<<j<<endl;
while(j && b[i] != a[j])
j = t[j-1];
if(b[i] == a[j])
j++;
if(j == strlen(a))
{
// out<<"found"<<endl;
p[ct++] = i - strlen(a) + 1;
j = t[j-1];
}
}
show();
return 0;
}