Pagini recente » Cod sursa (job #2821573) | Cod sursa (job #520857) | Cod sursa (job #266654) | Cod sursa (job #697374) | Cod sursa (job #2239623)
#include <bits/stdc++.h>
using namespace std;
char A[2000005], B[2000005];
int pi[2000005], n, m, pos[1024];
void compute_prefix()
{
int i, k = 0;
pi[1] = 0;
for (i = 2; i <= n; i++)
{
while((k > 0) && (A[k + 1] != A[k])){
k = pi[k];
}
if (A[k + 1] == A[i]){
k += 1;
}
pi[i] = k;
}
}
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i, q = 0, nr = 0;
f.get(A, sizeof(A));
f.get();
f.get(B, sizeof(B));
for (int i = 0; i < sizeof(A); i++){
if (A[i] >= 'a' && A[i] <= 'z' || A[i] >= 'A' && A[i] <= 'Z' || A[i] >= '0' && A[i] <= '9')
n++;
else break;
}
for (int i = 0; i < sizeof(B); i++){
if (B[i] >= 'a' && B[i] <= 'z' || B[i] >= 'A' && B[i] <= 'Z' || B[i] >= '0' && B[i] <= '9')
m++;
else break;
}
for (i = n; i ; i -- ){
A[i] = A[i - 1];
}
A[0] = ' ';
for (i = m; i ; i -- ){
B[i] = B[i - 1];
}
B[0] = ' ';
compute_prefix();
for (i = 1; i<= m; i++)
{
while ( q && A[q + 1] != B[i]){
q = pi[q];
}
if (A[q + 1] == B[i]){
++q;
}
if (q == n){
q = pi[n];
++ nr;
if ( nr <= 1000) {
pos[nr] = i - n;
}
}
}
g << nr << "\n";
for (i = 1; i <= nr; i++)
{
g << pos[i]<< " ";
}
return 0;
}